When Are GFlowNets Scalable? A Regret Analysis of Sample Efficiency

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 $d$, rather than the state space size. We first establish an oracle-sampling lower bound of $\Omega (\frac{dH}{1+\log d}\log (1+K/d))$. This bound reveals a data-starved regime: when $K\ll d$, the worst-case average performance gap does not vanish, so the trajectory budget must reach the scale $K=\Omega (d)$ 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 $d$-dimensional representation of policy values. A first-order analysis yields regret $O(dH\sqrt{K\log (1+K/d)})$, and a second-order analysis further improves the dependence on the trajectory budget $K$ 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 $d$ can approach the state space size. This provides a formal step toward the theory of the statistical scalability of GFlowNets.