Pessimistic Backward Policy for GFlowNets

Summary

The paper successfully identifies and addresses the under-exploitation problem in the flow matching of GFlowNets. The proposed method, Pessimistic Backward Policy (PBP-GFN), adjusts the probabilities of backward trajectories to improve exploration and exploitation, achieving superior performance in various benchmarks.

Strengths

- This paper first identifies the significant issue in conventional GFlowNets—under-exploitation due to unobserved flow in backward trajectories. - The paper provides a clear and detailed explanation of the methodology, including the training process and the loss function used for the backward policy.

Weaknesses

- The PBP-GFN introduces additional complexity to the training process of GFlowNets. Pessimistic training of backward policy might be computationally expensive or hard to tune in different settings. The author should discuss this in the updated version of the paper. - In the experiment sections, this paper does not compare with some new GFlowNets methods, such as [1, 2], that claim improvement over the baselines. I wonder (1) Are PBP-GFN's results better than [1, 2]? (2) Can we combine the pessimistic backward policy with strategies, such as those in [1, 2], to further improve performance? I understand that each paper deals with GFlowNets from a different perspective, therefore, I am ok if not all answers are yes. - There are some missing references that are also quite relevant to the topic. [3,4] - I would raise my scores if my concerns are resolved. [1] Kim, M., Yun, T., Bengio, E., Zhang, D., Bengio, Y., Ahn, S., & Park, J. (2023). Local search gflownets. arXiv preprint arXiv:2310.02710. [2] Jang, H., Kim, M., & Ahn, S. (2023). Learning Energy Decompositions for Partial Inference of GFlowNets. arXiv preprint arXiv:2310.03301. [3] Chen, Y., & Mauch, L. (2023). Order-Preserving GFlowNets. arXiv preprint arXiv:2310.00386. [4] Tiapkin, Daniil, et al. "Generative flow networks as entropy-regularized rl." International Conference on Artificial Intelligence and Statistics. PMLR, 2024.

Questions

- When minimizing the negative log-likelihood in Eq.5, how to ensure, or do we need to ensure that the sum of the backward probability on a state is 1, and why the total amount of backward flows will not change claimed in line 157? In the provided codebase "PBP.train_proxy", it seems the sum of log_pb_actions will change, and the total number of flows will change. - This paper includes MIS from [1]. Can you include more difficult graph combinatorial optimization problems from [1], such as maximum cut? (Maximum clique is not necessary since it is related to MIS) [1] Zhang, D., Dai, H., Malkin, N., Courville, A., Bengio, Y., & Pan, L. (2023). Let the flows tell: Solving graph combinatorial optimization problems with gflownets. arXiv preprint arXiv:2305.17010.

Rating

6

Confidence

3

Soundness

2

Presentation

3

Contribution

2

Limitations

Please see the **Weaknesses** part.

Summary

The authors present a problem with GFlowNets training that originates from not having seen backward trajectories for a particular terminal state. The authors show that because of the lack of observed trajectories, the backward flows underestimate the probabilities for the observed flows, resulting in a (forward) policy that may not match the reward distribution. The authors propose to mitigate the problem by increasing backward flows for the observed trajectories. The authors provide experimental results in eight different environments, showing the superior performances of their method in terms of mode discovery and distribution fitting.

Strengths

1. Well-written motivation for the problem described. 2. The solution presented is well-motivated and clearly described. 3. The experiments include well-studied environments and baselines, showing the method's performance in exploitation.

Weaknesses

1. The discussion about lacking backward flow given the unseen trajectories is valid. In practice, one can mitigate this by having a uniform backward policy with **a reward-prioritized replay buffer** [1], which also can increase the probability a trajectory yielding high rewards, thereby tackling the mentioned problem. I feel adding this baseline will improve the paper. 2. As an exploitation method, at least one experiment with a larger state-space should be useful to show its performance in larger state-spaces. Hypergrid with a larger dimension and horizon can be one option for this. [1] Shen, Max W., et al. "Towards understanding and improving gflownet training." International Conference on Machine Learning. PMLR, 2023.

Questions

1. What is the hypermeters for GAFN in Figure 9? Were the hyperparameters tuned for the experiments? 2. The example in Figure 3 raises a question: if $P_B(x|\tau)[i]$ is maximized, $P_B(x|\tau)[j] \approx 0; j \neq i$, thereby matching it will cause $P_F(x|\tau)[j] \approx 0; j \neq i$. In smaller state-space, it may not be a problem, but in a larger state-space, this should be an issue as it may cause $p(x) \approx 0$ where x necessitates action j whose probability we've just made approximately 0. Curious to hear what you think about this/whether you've done experiments in large-scale environments.

Rating

5

Confidence

4

Soundness

3

Presentation

3

Contribution

2

Limitations

Yes. Limitations are adequately addressed.

Summary

This paper proposes a pessimistic backward policy for GFlowNets (GFN), which maximizes the expectation of observed backward trajectories. This paper points out the under-exploitation of high-reward objects for previous GFN training methods and provides a deep analysis of this problem. Extensive experiments validate the superior performance of the proposed method.

Strengths

- This paper is well-written. The illustrations of the proposed method are clear, and the toy examples provided are easy to understand. - This paper proposes a simple yet effective method to address the problems of under-exploitation in GFN training. - Extensive experiments on 8 benchmarks validate the efficacy of the method.

Weaknesses

Does the auxiliary objective introduced in Eq. 5 affect the original GFN training objective? Since higher probabilities are assigned to the backward transitions of observed trajectories, could this impact the original assumptions of TB, DB, and other objectives? Do you observe instability during training after some episodes, once the model has seen a sufficient number of samples?

Questions

- How do you estimate Eq. 5 in practice? This is an important component of the method, but it is not described. - What's the meaning of $N$ in algorithm 1? Why does this method need multi-round gradient updates?

Rating

5

Confidence

3

Soundness

2

Presentation

3

Contribution

2

Limitations

Limitations have been discussed in this paper.

Summary

This paper addresses the under-exploitation of high-reward objects in Generative Flow Networks (GFlowNets) due to the limited observation of trajectories during training. The authors propose PBP-GFN (Pessimistic Backward Policy for GFlowNets), which modifies the backward policy to maximize the observed backward flow, aligning it closer to the true reward. They argue that this pessimistic training scheme encourages the forward policy to assign higher probabilities to high-reward objects, even if they are under-represented in the observed trajectories. Experiments across eight benchmarks, including hypergrid, molecule, and RNA sequence generation, demonstrate that PBP-GFN improves the discovery of high-reward objects while maintaining object diversity.

Strengths

* The paper tackles an important issue in GFlowNet training – the potential for under-exploration of high-reward objects due to the sparsity of observed trajectories. This issue is particularly relevant in complex domains with vast trajectory spaces. * The proposed solution, PBP-GFN, is conceptually simple and intuitive. Maximizing the observed backward flow to align with the true reward directly addresses the identified problem of under-exploitation. * The paper provides extensive experimental results across a variety of tasks, showcasing the effectiveness of PBP-GFN in enhancing the discovery of high-reward objects.

Weaknesses

* While the intuition behind PBP-GFN is clear, the paper lacks a strong theoretical analysis to support its claims. The "error bound" analysis in Appendix A is limited in scope and doesn't offer a comprehensive understanding of the algorithm's convergence properties or its impact on the target Boltzmann distribution. * The core idea of modifying the backward policy in GFlowNets has been explored in prior works [1, 2, 15]. PBP-GFN, while achieving promising empirical results, doesn't present a significant conceptual departure from these existing approaches. Its primary contribution appears to be a specific strategy for maximizing the observed backward flow, but the paper lacks a detailed comparison and analysis of how this strategy differs from or improves upon existing techniques. * The paper primarily focuses on metrics like the number of modes discovered and the average top-100 score. While these metrics are relevant for measuring exploration and exploitation, they provide a limited view of the overall quality and diversity of generated samples. Evaluating PBP-GFN on more comprehensive downstream task-specific metrics would strengthen the paper's claims. * While the paper claims that PBP-GFN maintains object diversity, the pessimistic training scheme inherently introduces a bias towards the observed trajectories. This bias could potentially lead to a reduction in exploration and the generation of degenerate or less diverse samples, especially in domains with significant uncertainty or where observed trajectories are not truly representative of the target distribution. A deeper analysis and empirical evaluation of this potential bias would be useful. * The performance of PBP-GFN heavily relies on the quality and representativeness of the observed trajectories. In scenarios where the initial observed trajectories are biased or incomplete, PBP-GFN could amplify these biases, hindering the discovery of truly novel and high-reward objects. The paper doesn't address this sensitivity or propose mitigation strategies. * The paper mainly compares PBP-GFN with other backward policy design methods. However, it doesn't provide a thorough comparison with other exploitation-focused techniques in GFlowNets, such as local search GFlowNets [3] or those focusing on higher-reward trajectories [2]. This limited comparison weakens the paper's claim of achieving superior performance in discovering high-reward objects. [1] Trajectory balance: Improved credit assignment in gflownets [2] Towards understanding and improving gflownet training. [3] Local search gflownets [4] Maximum entropy gflownets with soft q-learning

Questions

Please refer to weaknesses section above.

Rating

3

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

N/A.