I am reading the Yoshua Bengio et al, Flow Network based Generative Models for Non-Iterative Diverse Candidate Generation. It seems to me the objective of the paper is to generate the flow $F$ given the reward function $R(s)$ that satisfies the detailed balance constraint Equation (4). This can be easily solved by walking backwards from the terminal nodes and accumulating reward along the way. When the incident action edge is not unique the flow solution is not unique and in fact uncountably infinite number of them. The computational complexity of this algorithm is obviously linear with respect to the number of states.

What is the rationale for devising an objective function such as Equation (12) which is computationally complex to solve the problem?


1 Answer 1


If the state-space is small, you could indeed solve by dynamic programming (which would require visiting all the states, though). In exponentially large state-spaces (which are the ones you care about in AI), it would not work, and the objectives proposed in the paper are ways around that using the generalization power of deep learning or other ML approaches that can generalize thanks to inductive biases. In spirit, this is similar to how you solve the Bellman equation with TD-learning (which is a form of implicit -by opposition to explicit- dynamic programming), but where the fixed point is the flow-matching constraint rather than the Bellman equation.

  • 1
    $\begingroup$ Wow, I am lucky getting the answer from the horse's mouth! Thank you, Professor Bengio! I have upvoted and accepted your answer. I have a followup question stats.stackexchange.com/q/554492/44368. It would be greatly appreciated if you would be so kind as to answer that as well. $\endgroup$
    – Hans
    Dec 2, 2021 at 6:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.