acceptodds
Withdrawn from ICLR 2027

When Are GFlowNets Scalable? A Regret Analysis of Sample Efficiency

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Generative Flow Networks (GFlowNets) are designed to learn distributions over combinatorial objects whose underlying state spaces can be prohibitively large. While substantial progress has been made in improving GFlowNet training, through better trajectory sampling, exploration, and gradient estimation, a basic theoretical question remains unsolved: *when is a GFlowNet statistically scalable, and how does the structure of the task determine its sample efficiency?* We study this question through regret, where the performance gap is the trajectory KL divergence from the reward-proportional target distribution. Our central finding is that the relevant statistical scale is the representation dimension , rather than the state space size. We first establish an oracle-sampling lower bound of . This bound reveals a data-starved regime: when , the worst-case average performance gap does not vanish, so the trajectory budget must reach the scale to leave this regime. We then investigate whether the statistical scaling of the lower bound can be approached constructively. We develop an optimistic policy-learning algorithm that leverages a shared -dimensional representation of policy values. A first-order analysis yields regret , and a second-order analysis further improves the dependence on the trajectory budget to be logarithmic under the stated assumptions. Together, these results identify representation dimension as a fundamental measure of GFlowNet learnability: enormous state spaces of GFlowNet can remain statistically scalable when their relevant value structure admits a compact shared representation, whereas without such compression the effective dimension can approach the state space size. This provides a formal step toward the theory of the statistical scalability of GFlowNets.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Generative Flow Networks, Sample efficiency, Regret analysis, Optimistic policy optimization.

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_tv59OpenReview ↗
Rating
3
Confidence
1
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

The paper explores the statistical scalability of GFlowNets. The primary contributions are the derivation of a theoretical lower bound on regret, followed by first-order and second-order analyses establishing upper bounds for a proposed learning algorithm. These bounds characterise the statistical scalability of GFlowNets in terms of the representation dimension (d), trajectory horizon (H), and number of training trajectories (K), rather than explicitly depending on the potentially enormous size of the underlying state space (|S|). The analysis also identifies a minimum sample requirement related to d, while the second-order upper bound demonstrates logarithmic dependence on the number of training trajectories K. The conclusion is that GFlowNets can remain statistically scalable even with enormous state spaces, provided their underlying value structure can be captured by a compact shared representation. Without such compression, the effective representation dimension d may grow to be comparable to the size of the state space.

Critical strengths
  1. The paper addresses a fundamental question of GFlowNets and provides comprehensive theoretical analysis.

  2. While the paper is dense with math, I find the non-math parts easy to read, and the paper is well structured and motivated.

Critical weaknesses
  1. Assuming the derivations are correct, would the lower and upper bounds derived in the paper, which scale with d, H, and K, sufficiently demonstrate that GFlowNet scalability is not dependent on |S|? First, could d and H themselves scale with |S|, meaning that more complex learning problems may naturally require larger representations and longer trajectories? Second, while the derived bounds do not explicitly depend on |S|, could other characteristics of the state-space structure still be relevant to a tighter characterisation of learning difficulty? Third, |S| and H may be correlated in certain construction graphs, so a large H could also imply a large |S|. I wonder whether the paper sufficiently distinguishes between demonstrating scalability under the stated assumptions and establishing that scalability is fundamentally independent of |S|.

  2. Practical significance and empirical demonstration. The paper stops right after the second-order proof. It would be useful to demonstrate, at least through a toy example, what the identified K = Ω(d) sample requirement looks like in practice, particularly how the average regret changes around the data-starved regime. Also, what is considered a practical choice of d, and how would such a compact representation be obtained for an actual GFlowNet task? It would also be interesting to demonstrate whether increasing |S| while keeping d fixed would produce the expected scalability behaviour.

Questions for authors

While my mathematical background does not allow me to fully verify the correctness of the proofs, I find the paper generally interesting. My first question in Weakness 1 is perhaps more about the definitive tone of the paper in claiming that GFlowNet scalability depends on d rather than |S|. The second question is more about gaining a practical understanding of how the theoretical results should be interpreted and evaluated in real-world settings. Nevertheless, I remain positive about the paper.

7 comments
AuthorsOpenReview ↗

Response to Weakness (Part 1)

First of all, we would like to express our sincere gratitude for your encouraging and constructive comments.

  1. We would like organize our response into three aspects (1) notation and representation dimension, (2) the fundamental challenge of GFlowNet learning, and (3) the direct answer your questions.

    • The dd is the per-layer representation dimension of Sh\mathcal S_h, rather than the whole state space S=∪ Sh\mathcal S=\cup\, \mathcal S_h. Different layers may have different representation dimensions dhd_h; for notational simplicity, we use a common dimension dd.

      We have uploaded a revised manuscript to make this clearer in the assumption 2.2 (previously Assumption 4.4). Besides, We have also clarified the Bellman representation as $ V(s')=\phi_{h+1}(s')^\top\theta_{h+1}(V)$, instead of the previous notation V(s′)=ϕh(s,s′)⊤θh(V)V(s')=\phi_h(s,s')^\top\theta_h(V). Since the continuation value depends only on the successor state (s'), the revised formulation explicitly reflects the intended successor-state representation without changing our theoretical analysis.

    • In the GFlowNet setting, only the reward RR over terminal space SH:=X\mathcal S_{H}:=\mathcal{X} is externally specified by the task. The fundamental challenge is that the terminal state space X\mathcal X can be prohibitively large, making exact marginalization and direct sampling from P⋆(x)=R(x)/Z⋆P^\star(x)=R(x)/Z^\star computationally intractable. The DAG construction (S0,…,SH−1\mathcal S_0,\ldots, \mathcal S_{H-1}) and intermediate reward ρ(s,s′)\rho(s,s') (i.e. the logorithm of backward policy, log⁡π←(s∣s′)\log \overleftarrow\pi(s|s')) are specified by the users, and therefore are not considered as the sources of challenge.

      Our objective is to formally characterize structural conditions under which GFlowNet learning can scale with an effective representation dimension rather than the cardinality of the state space, thereby providing a theoretical pathway toward addressing this challenge. Especially, at the terminal stage, our linear Bellman representation assumption requires

      VH(x)=log⁡R(x)=ϕH(x)⊤θH,θH∈RdV_H(x)=\log R(x)=\phi_H(x)^\top\theta_H,\qquad \theta_H\in\mathbb R^d,

      where potentially d≪∣X∣d\ll|\mathcal X|. The significance of this assumption is that values associated with an enormous number of states can be represented through only dd coefficients per stage. Consequently, information collected from visited states can generalize to unvisited states through their shared representation.

    • Returning to your questions:

      • dd measures the effective representation dimension of each layer, whereas HH is the numer of total layers of user-specified DAG construction. So dd is a direct alternative of ∣Sh∣|\mathcal S_h|, and neither dd or ∣Sh∣|\mathcal S_h| depends on HH;

      • As clarified above, the fundamental challenge in GFlowNet learning is the potentially enormous terminal state space (mainly X\mathcal X as the intermediate reward . Therefore, analyzing the state space compressibility provides a direct theoretical approach to understanding when GFlowNet learning can be sample-efficient.

      • As explained above, dd is identified as the compressed dimension for each layer Sh\mathcal S_h, (especially for SH\mathcal S_H). Therefore, dd and S\mathcal S does not involve HH. A large HH may give a large set of (S0,…,Sh−1)(S_0,\ldots, S_{h-1}). However, expect X\mathcal X and RR, (S0,…,Sh−1)(S_0,\ldots, S_{h-1}) and associated reward ρ(sh,sh+1)\rho(s_h,s_{h+1}) is freely specified by the user to facilitate the modeling over (X,R)(\mathcal X, R), thereby not considered as the bottleneck of GFlownet learning in general.

      Finally, our lower and upper bounds already take your concern into account: both identify regret linear dependence on dHdH or dH2dH^2. Here, dHdH represents the total representation dimension across all HH layers. As demonstraed in our proof precedure, the appearing of factor HH or H2H^2, just arises from accumulating the regret contributions at each layer h∈[1,H]h\in [1, H].

AuthorsOpenReview ↗

Response to Weakness (Part 2)

  1. We thank the reviewer for this constructive suggestion. We agree that empirical illustrations would help demonstrate the practical implications of our theoretical results. We would like to response this from three perspectives:( 1) our theoretical contributions, (2) connections to practical GFlowNet algorithms, and (3) supporting empirical evidence from existing studies.

    (1). Since the sources of GFlowNet diffuculty is the enormous size of X\mathcal X. The bottlneck can be understood as how to efficiently epxlorate the state space, so that the exact enumerate of all state is avoided. The lower-bound setting eliminates this exploration difficulty by allowing oracle samples directly from the target distribution, so that a regret benchmark is establised. Our upper-bound algorithm has no access to such oracle information and aim at addressing the exploration challenge by constructing a deterministic confidence width, Γhk(s,s′)=λL∥ϕh+1(s′)∥(Λhk)−1\Gamma_h^k(s,s')=\sqrt{\lambda}L\left\|\phi_{h+1}(s')\right\|_{(\Lambda_h^k)^{-1}}.

    • This bonus leverages information from visited states and the shared low-dimensional Bellman representation to construct globally valid confidence bounds for both visited and unvisited states. Under our assumptions, these bounds yield optimistic value estimates satisfying Vhk(s)≥Vh⋆(s)≥Vhπk(s)V_h^k(s)\ge V_h^\star(s)\ge V_h^{\pi^k}(s) for all states, thereby enabling efficient exploration of unvisited regions through optimistic policy updates.

    • We acknowledge that our regression formulation is idealized. In practical neural GFlowNets, the representation and its coefficients ϕ⊤θ\phi^\top\theta are jointly represneted by neural networks. The confidence width λL∣ϕh+1(s′)∣(Λhk)−1\sqrt{\lambda}L|\phi_{h+1}(s')|_{(\Lambda_h^k)^{-1}} may not be readlity obtained or automatically guaranteed, when the representation itself is learned by aneural networks.

    • Nevertheless, our analysis provides a theoretical explanation for how neural GFlowNets may succeed in seemingly intractable combinatorial spaces: when the underlying task admits a sufficiently compact representation and the network successfully captures this structure, information acquired from sampled trajectories can generalize to a much larger collection of unvisited states. In other words, without such a compact representation, GFlowNet learning may become computationally intractable. Our confidence-based optimism provides an idealized theoretical mechanism for uncertainty-guided generalization and exploration.

    (2). Furthermore, we have added Appendix F: Theoretical Insights into Practical GFlowNet Training, which establishes a direct mathematical connection between our Bellman residual analysis and commonly used GFlowNet training objectives, including Subtrajectory Balance (Sub-TB), Detailed Balance (DB) and Trajectory Balance (TB). In particular, define the optimistic Bellman residual by δhk:=Whk(sh,sh+1)−log⁡PB(sh∣sh+1)−Vh+1k(sh+1)\delta_h^k:=W_h^k(s_h,s_{h+1}) - \log P_B(s_h\mid s_{h+1})- V_{h+1}^k(s_{h+1}) (we previously use $Q_h^k(\cdot,\cdot) $ ). Using the implicit flow representation Fhk(s)=exp⁡Vhk(s)F_h^k(s)=\exp V_h^k(s), we establish the identity

    \begin{aligned} \delta_{\mathrm{SubTB}}^k(\tau_{i:j})&=\log\frac{F_i^k(s_i)P_{\pi^k}(\tau_{i:j}\mid s_i)}{F_j^k(s_j)P_B(\tau_{i:j}\mid s_j)}= \sum_{h=i}^{j-1}\delta_h^k(s_h,s_{h+1}). \end{aligned}

    The classical Detailed Balance (DB) and Trajectory Balance (TB) residuals are recovered by taking j=i+1j=i+1 and (i,j)=(0,H)(i,j)=(0,H), respectively. Consequently, our second-order Bellman residual analysis also yields cumulative flow-balance error bounds associated with these practical training objectives. This correspondence demonstrates that our theoretical framework is closely connected to the flow-consistency principles underlying practical GFlowNet algorithms, even though their neural implementations need not satisfy our fixed-feature assumptions.

AuthorsOpenReview ↗

Response to Weakness (Part 3)

  1. (Continue)

    (3). A more concrete empirical illustration of exploiting task structure is SUBo-GFN (Signal from Structure: Exploiting Submodular Upper Bounds in Generative Flow Networks, Larouche and Durand, 2026), which leverages the submodularity of reward functions.

    • By the diminishing-returns property, for an unobserved terminal object xx, an element a∈xa\in x, and s⊊x∖as\subsetneq x\setminus{a}, the reward satisfies

      R(x)≤R(s∪a)−R(s)+R(x∖a)⏟UB(x∣s,a)R(x)\le\underbrace{R(s\cup{a})-R(s)+R(x\setminus{a})}_{\mathrm{UB}(x\mid s,a)}.

      Since VH(x)=log⁡R(x)V_H(x)=\log R(x), this provides an optimistic upper bound on the terminal value:

      VH(x)≤log⁡UB(x∣s,a)V_H(x)\le\log\mathrm{UB}(x\mid s,a).

      The reasoning is that only terminal reward R(x)R(x) is externally specified by the task, whereas the DAG construction (S0,…,SH−1\mathcal S_0,\ldots, \mathcal S_{H-1}) ad intermediate reward ρ(s,s′)\rho(s,s') (i.e. the logorithm of backward policy, log⁡π←(s∣s′)\log \overleftarrow\pi(s|s')) are specified by the users, and are not considered as the sources of learning challenge. Therefore, SUBo-GFN only focus on bounding the terminal values (i.e. rewards) for algorithm simplicity.

    • This inequality allows previously observed rewards to provide upper bounds on the rewards of unvisited combinatorial objects, without explicitly evaluating every terminal state. In their submodular graph experiments, SUBo-GFN reports approximately 30–171 times more terminal states receiving informative training signals than conventional GFlowNets, together with improved distribution-matching performance.

    • This mechanism is conceptually analogous to the optimism bonus in our framework, where the low-dimensional Bellman representation and deterministic regression confidence bound yield

      Vh+1k(s′)≤ϕh+1(s′)⊤whk+Γhk(s,s′)⏟Optimistic continuation-value estimateV_{h+1}^k(s')\le\underbrace{\phi_{h+1}(s')^\top w_h^k+\Gamma_h^k(s,s')}_{\text{Optimistic continuation-value estimate}}

      with λL∣ϕh+1(s′)∣(Λhk)−1\sqrt{\lambda}L|\phi_{h+1}(s')|_{(\Lambda_h^k)^{-1}}. Our framework extends this structural generalization to continuation values at every stage, enabling recursive optimism and end-to-end regret analysis under a mathematically tractable low-dimensional Bellman representation assumption.

    Therefore, while SUBo-GFN focus on practical implementable under the optimism-under-uncertainty principle, our work formalizes this principle through a more explicit and mathematically tractable low-dimensional Bellman representation assumption, establishing corresponding regret guarantees. This perspective also offers a possible theoretical explanation for the success of GFlowNets that do not explicitly incorporate task-specific structural properties.

    We acknowledge that these existing experiments do not directly verify the predicted behavior around K≈dK\approx d or the effect of increasing ∣Sh∣|\mathcal S_h| while holding dd fixed. Our contribution is a generalized theoretical characterization of these phenomena, and controlled empirical validation remains a valuable direction for future work.

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

This paper investigates the sample efficiency of GFlowNets using regret analysis, where regret directly measures the cumulative generative error between the learned trajectory distributions and the target distribution. The authors first establish a lower bound on regret when learning from samples of the target distribution. They then propose an optimistic algorithm that assumes a linear representation of the value function and prove an upper bound on regret. The main conclusion is that the statistical scalability of GFlowNets depends on the representation dimension dd, rather than directly on the size of the state space.

Critical strengths
  1. Going beyond the size of the state space. The environments in which GFlowNets are typically trained have combinatorially large state spaces. Analyzing regret in terms of the structure of the task, rather than the size of the state space, to determine sample efficiency is an interesting approach. To my knowledge, there has not been a similar analysis in the GFlowNet literature.

  2. Second-order regret analysis. The authors use the negative KL term in the regret decomposition to obtain a second-order bound. This provides an interesting connection between optimistic value estimation, entropy regularization, and logarithmic regret under realizability assumptions.

Critical weaknesses
  1. Lower and upper bounds under different information models. Although the authors make this clear in the paper, I think this is the main weakness of the work. In the lower bound, the learner receives samples directly from the target distribution, while in the upper bound, the learner uses on-policy samples, knows the feature map, reward and backwards policy, and can evaluate the value function VV. This mismatch between the lower and upper bounds models makes me question whether dd is really the fundamental scale of the problem.

  2. Inconsistent meaning of dd. The notation dd seems to be Inconsistent. In the upper bound, dd is the dimension of a known feature map, while in the lower bound, dd is the number of unknown parameters per block in the tree construction, with a total of dBdB parameters. The paper does not show that the hard instance used in the lower bound satisfies Assumption 4.1 with representation dimension dd.

Questions for authors
  1. Horizon dependence. How do the constants gg and LL scale with the trajectory length?

  2. Empirical examples. It would be interesting to see some empirical examples of the proposed results. The paper starts with the idea that, instead of looking at the size of the state space, sample efficiency can be analyzed in terms of the structure of the task. It would be interesting to see a practical example of this, even in a toy environment.

6 comments
AuthorsOpenReview ↗

Response to weakness

Before addressing your comments, we would like to thank you for your constructive feedback and note that we have uploaded a revised version of the manuscript. In particular, we have clarified the Bellman representation by writing $ V(s')=\phi_{h+1}(s')^\top\theta_{h+1}(V)$, instead of the previous notation V(s′)=ϕh(s,s′)⊤θh(V)V(s')=\phi_h(s,s')^\top\theta_h(V). Since the continuation value V(s′)V(s') depends only on the successor state s′s', the dependence on the preceding state ss in the previous formulation is redundant. This notational clarification improves consistency throughout the manuscript without affecting the validity of our theoretical results.

  1. We thank the you for highlighting this concern. We would first like to clarify that we have revised the lower-bound construction to strengthen its consistency with the upper-bound assumptions.

    • The revised hard-instance construction now satisfies Assumption 2.2 (previously Assumption 4.4), including the known, low-dimensional Bellman representation. Moreover, the terminal reward is fixed and known, and the backward policy is accessible through exact local queries, consistent with the upper-bound setting. Under a local-query budget Qlower=O(dH)Q_{\mathrm{lower}}=O(dH), the revised Theorem 3.1 establishes

      inf⁡Asup⁡θEθ[Reg⁡⋆(K)]=Ω(dHlog⁡(1+Kd)),\inf_{\mathbb A}\sup_\theta\mathbb E_\theta[\operatorname{Reg}^\star(K)]=\Omega\left(dH\log\left(1+\frac Kd\right)\right),

    • In the on-policy setting, our algorithm exploits the same type of low-dimensional Bellman representation through exact relabeling, Vh+1(s′)=ϕh+1(s′)⊤θh+1(V)V_{h+1}(s')=\phi_{h+1}(s')^\top\theta_{h+1}(V), yielding the second-order regret guarantee $ \mathbb E[\operatorname{Reg}(K)]=O(H^2d\log\left(1+\frac{K}{\lambda d}\right)$.

    • Importantly, the query-budget scales are compatible in the data-starved regime K≤dK\le d. The online algorithm requires O(H)O(H) local backward-policy evaluations per trajectory for forward sampling, giving $ Q_{\mathrm{upper}}=O(HK)=O(dH)$ for K≤dK\le d, which is consistent with the lower-bound query-budget scale.

  • We agree that establishing a minimax lower bound under the same online-sampling model would provide a more direct comparison with our upper bound. However, our target-sampling oracle provides stronger sampling access by granting the learner, trajectories directly from the optimal distribution P⋆P^\star, which is precisely the distribution that GFlowNets aim to learn. This choice eliminates the exploration difficulty entirely, whereas efficiently exploring an enormous combinatorial state space is the central challenge in GFlowNet learning.

    Accordingly, without access to target-oracle samples, the central idea of our upper-bound algorithm is to leverage information from visited states and the shared low-dimensional Bellman representation to construct globally valid confidence bounds for both visited and unvisited states, using exploration bonuses Γhk(s,s′)\Gamma_h^k(s,s'). Under our assumptions, these bounds yield optimistic value estimates satisfying Vhk(s)≥Vh⋆(s)≥Vhπk(s)V_h^k(s)\ge V_h^\star(s)\ge V_h^{\pi^k}(s) for all states, thereby enabling efficient exploration of unvisited regions through optimistic policy updates.

  • This oracle formulation also offers a simpler mathematical construction and greater algorithmic generality. In particular, the lower bound applies to arbitrary policy estimators and is independent of the specific learning algorithm used to establish the upper bound. Thus, the lower-bound analysis remains applicable even if the upper-bound algorithm is modified or replaced.

  1. Thank you for pointing out this important issue. We agree that the previous version did not clearly distinguish the number of unknown parameters in the lower-bound construction from the representation dimension used in the upper-bound analysis. Moreover, the previous proof did not explicitly verify that the hard instance satisfied the linear Bellman representation assumption.

    We have addressed both concerns in the revised manuscript by clarifying the definition of the representation dimension and redesigning the lower-bound construction. In the revised manuscript, dd consistently denotes the dimension of the known feature map at each Bellman stage (Assumption 2.2), rather than the total number of unknown parameters in the GFlowNet.

    • In the revised lower-bound construction, we define p=⌊d/2⌋p=\lfloor d/2\rfloor and B=⌊H/4⌋B=\lfloor H/4\rfloor, representing the number of forward marginal coordinates per block and the number of blocks, respectively. Although the construction contains BpMBpM unknown backward-policy entries, we explicitly prove in Lemma A.1 of Appendix A.1 that the Bellman values at every stage admit a known linear representation of dimension at most 2p≤d2p\le d.

    • Lemma A.1 also explicitly proves that the lower-bound construction satisfies Assumption 2.2 for feasture map and finite radius LL.

AuthorsOpenReview ↗

Response to question (Part 1)

Q1. Thank you for raising this question. We agree that stating that the clipping-range parameter gg and the representation coefficient cL=L/dc_L=L/\sqrt d as problem-dependent constants may obscure their dependence on the horizon HH.

  1. First, the clipping intervals defined in Lemma B.1 yield g=max⁡h(uh−ℓh)=(ι‾−ι‾)+H(ρ‾−ρ‾)+(H−1)log⁡amax⁡g=\max_h(u_h-\ell_h) =(\overline\iota-\underline\iota)+H(\overline\rho-\underline\rho)+(H-1)\log a_{\max}. Thus, we have g=O(H)g=O(H).We will make this distinction explicit in the revised version.

  2. Second, the coefficient radius LL and representation in Assumption 2.2 is defined for the Bellman representation at each individual stage, rather than for a representation aggregated over all HH stages. Each stage hh may have its own coefficient bound LhL_h and dhd_h. For notational simplicity, we use a common bound L=max⁡h∈[H]0LhL=\max_{h\in[H]_0}L_h. Therefore, no additional factor of HH explicit arises in LL. In typical GFlowNet DAGs, the terminal layer SH=X\mathcal S_H=\mathcal X is often the largest, and hence may determine the maximal representation dimension dd and coefficient radius LL.

Q2. We thank the reviewer for this suggestion. We agree that empirical illustrations are valuable for understanding how task structure can improve GFlowNet sample efficiency. We would like anwer this question from three complementary perspectives: (1) our theoretical contributions, (2) connections to practical GFlowNet algorithms, and (3) supporting empirical evidence from existing studies.

  1. The fundamental challenge in GFlowNet learning is that the combinatorial terminal space SH=X\mathcal S_{H}=\mathcal X, can be prohibitively large to enumerate, making exact marginalization and direct sampling from the reward-proportional distribution P⋆(x)=R(x)/Z⋆P^\star(x)=R(x)/Z^\star computationally intractable in general. The DAG construction (S0,…,SH−1\mathcal S_0,\ldots, \mathcal S_{H-1}) ad intermediate reward ρ(s,s′)\rho(s,s') (i.e. the logorithm of backward policy, log⁡π←(s∣s′)\log \overleftarrow\pi(s|s')) are specified by the users, and therefore are not considered as the sources of challenge.

    Our objective is to formally characterize structural conditions under which GFlowNet learning can scale with an effective representation dimension rather than the cardinality of the state space, thereby providing a theoretical pathway toward addressing this challenge. Specifically, at the terminal stage, our linear Bellman representation assumption requires

    $ V_H(x)=\log R(x)=\phi_H(x)^\top\theta_H,\qquad \theta_H\in\mathbb R^d$,

    where potentially d≪∣X∣d\ll|\mathcal X|. The significance of this assumption is that values associated with an enormous number of states can be represented through only dd coefficients per stage. Consequently, information collected from visited states can generalize to unvisited states through their shared representation.

AuthorsOpenReview ↗

Response to Question (Part 2)

  1. We acknowledge that our regression formulation is idealized. In practical neural GFlowNets, the representation and its coefficients ϕ⊤θ\phi^\top\theta are jointly represneted by neural networks, and the confidence width λL∣ϕh+1(s′)∣(Λhk)−1\sqrt{\lambda}L|\phi_{h+1}(s')|_{(\Lambda_h^k)^{-1}} may not be readlity obtained and guaranteed, for keeping the optimism over unobsered states when constructing πk\pi^k.

    Nevertheless, our analysis provides a theoretical explanation for how neural GFlowNets may succeed in seemingly intractable combinatorial spaces: when the underlying task admits a sufficiently compact representation and the network successfully captures this structure, information acquired from sampled trajectories can generalize to a much larger collection of unvisited states. In other words, without such a compact representation, GFlowNet learning may become computationally intractable. Our confidence-based optimism provides an idealized theoretical mechanism for uncertainty-guided generalization and exploration.

    Furthermore, we have added Appendix F: Theoretical Insights into Practical GFlowNet Training, which establishes a direct mathematical connection between our Bellman residual analysis and commonly used GFlowNet training objectives, including Subtrajectory Balance (Sub-TB), Detailed Balance (DB) and Trajectory Balance (TB). In particular, define the optimistic Bellman residual by δhk:=Whk(sh,sh+1)−log⁡PB(sh∣sh+1)−Vh+1k(sh+1)\delta_h^k:=W_h^k(s_h,s_{h+1}) - \log P_B(s_h\mid s_{h+1})- V_{h+1}^k(s_{h+1}) (we previously use $Q_h^k(\cdot,\cdot) $ ). Using the implicit flow representation Fhk(s)=exp⁡Vhk(s)F_h^k(s)=\exp V_h^k(s), we establish the identity

    \begin{aligned} \delta_{\mathrm{SubTB}}^k(\tau_{i:j})&=\log\frac{F_i^k(s_i)P_{\pi^k}(\tau_{i:j}\mid s_i)}{F_j^k(s_j)P_B(\tau_{i:j}\mid s_j)}= \sum_{h=i}^{j-1}\delta_h^k(s_h,s_{h+1}). \end{aligned}

    The classical Detailed Balance (DB) and Trajectory Balance (TB) residuals are recovered by taking j=i+1j=i+1 and (i,j)=(0,H)(i,j)=(0,H), respectively. Consequently, our second-order Bellman residual analysis also yields cumulative flow-balance error bounds associated with these practical training objectives. This correspondence demonstrates that our theoretical framework is closely connected to the flow-consistency principles underlying practical GFlowNet algorithms, even though their neural implementations need not satisfy our fixed-feature assumptions.

  2. A concrete empirical illustration of exploiting task structure is SUBo-GFN (Signal from Structure: Exploiting Submodular Upper Bounds in Generative Flow Networks, Larouche and Durand, 2026), which leverages the submodularity of reward functions. By the diminishing-returns property, for an unobserved terminal object xx, an element a∈xa\in x, and s⊊x∖as\subsetneq x\setminus{a}, the reward satisfies

    R(x)≤R(s∪a)−R(s)+R(x∖a)⏟UB(x∣s,a)R(x)\le\underbrace{R(s\cup{a})-R(s)+R(x\setminus{a})}_{\mathrm{UB}(x\mid s,a)}.

    Since VH(x)=log⁡R(x)V_H(x)=\log R(x), this provides an optimistic upper bound on the terminal value:

    VH(x)≤log⁡UB(x∣s,a)V_H(x)\le\log\mathrm{UB}(x\mid s,a).

    The reasoning is that only terminal reward R(x)R(x) is externally specified by the task, whereas the DAG construction (S0,…,SH−1\mathcal S_0,\ldots, \mathcal S_{H-1}) ad intermediate reward ρ(s,s′)\rho(s,s') (i.e. the logorithm of backward policy, log⁡π←(s∣s′)\log \overleftarrow\pi(s|s')) are specified by the users, and are not considered as the sources of learning challenge. Therefore, SUBo-GFN only focus on bounding the terminal values (i.e. rewards) for algorithm simplicity.

    This inequality allows previously observed rewards to provide upper bounds on the rewards of unvisited combinatorial objects, without explicitly evaluating every terminal state. In their submodular graph experiments, SUBo-GFN reports approximately 30–171 times more terminal states receiving informative training signals than conventional GFlowNets, together with improved distribution-matching performance.

    This mechanism is conceptually analogous to the optimism bonus in our framework, where the low-dimensional Bellman representation and deterministic regression confidence bound yield

    Vh+1k(s′)≤ϕh+1(s′)⊤whk+Γhk(s,s′)⏟Optimistic continuation-value estimateV_{h+1}^k(s')\le\underbrace{\phi_{h+1}(s')^\top w_h^k+\Gamma_h^k(s,s')}_{\text{Optimistic continuation-value estimate}}

    with λL∣ϕh+1(s′)∣(Λhk)−1\sqrt{\lambda}L|\phi_{h+1}(s')|_{(\Lambda_h^k)^{-1}}. Our framework extends this structural generalization to continuation values at every stage, enabling recursive optimism and end-to-end regret analysis under a mathematically tractable low-dimensional Bellman representation assumption.

    Therefore, while SUBo-GFN focus on practical implementable under the optimism-under-uncertainty principle, our work formalizes this principle through a more explicit and mathematically tractable low-dimensional Bellman representation assumption, establishing corresponding regret guarantees. This perspective also offers a possible theoretical explanation for the success of GFlowNets that do not explicitly incorporate task-specific structural properties.

Reviewer_Sc37OpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The paper studies the number of trajectories required to learn a GFlowNet on a large graph. The authors use connections between Gflownets and entropy-regularized RL to reduce the regret bound to the cumulative KL divergence between the learned and target trajectory distributions. The paper derives a lower bound when only target trajectories are observed. Then the authors propose an optimistic regression algorithm under the linear Bellman representation assumption.

Critical strengths

The lower bound of section 3 seems to be novel in the context of GFlowNet literature, albeit it is based on rather classical statistical arguments.

Critical weaknesses
  1. The strongest problem is the comparison between the lower and upper bounds. In the lower bound, the learner observes target trajectories without knowing the reward function. Algorithm 1 can evaluate rewards. The lower bound therefore does not show that Algorithm 1 needs the claimed number of trajectories.

  2. Assumption 4.1 requires substantially more than a compact representation of the optimal value. Namely, it assumes that the same feature space must represent every optimistic value generated during learning. Learning at the same time involves bonuses, clipping, and softmax computations, which do not preserve a linear function class. The paper provides no particular family of large graphs where this condition holds with small, known dd.

Questions for authors
  1. Can the lower and upper bounds be formulated with the same information access and the same known features representation?

  2. Could the authors provide one particular family of large graphs satisfying Assumption 4.1 with small dd, including all values generated by Algorithm 1? Is it some chance that some modification of real world Gflownet benchmarks satisfy these assumptions?

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

Related papers

Discussion (0)

Sign in to comment.