Pessimistic Backward Policy for GFlowNets

Dear reviewer WPBt,

We express our deep appreciation for your time and insightful comments. In what follows, we address your comments one by one.

---

W1. The PBP-GFN introduces additional complexity, which may be expensive or inpractical in some settings. Can the authors provide a discussion on this point?

We clarify that the training of the pessimistic backward policy does not require significant overhead and is practical in most cases, as it only requires computing the gradients of the negative log-likelihood for the given trajectories. This requires similar or higher complexity than the conventional backward policy but less than the sub-structure backward policy. Especially, this complexity (i.e., the computation of gradients) would be minor for real-world problems with expensive reward evaluations, e.g., molecular docking tools or wet-lab experiments. We will update our future manuscript to reflect these points.

---

W2. Compared to independent lines of research for exploitation, e.g., local search GFN and LED-GFN, (A) does PBP-GFN show superior results, and (B) can we combine PBP-GFN with these approaches to further improve performance?

To address your comments, we conducted new experiments by (A) comparing PBP-GFN with local search and LED-GFN and (B) combining PBP-GFN with them. Note that (B) is trivial since our pessimistic backward policy is orthogonal to local search and LED-GFN that address off-policy sampling and local credits.

We present the results in Figure C(a) and Figure D(a) of our rebuttal PDF. One can see that PBP-GFN (A) shows similar performance compared to local search GFN and LED-GFN, and (B) further improves performance when combined with them.

---

W3. There are some missing references that are also quite relevant to the topic [2,3].

Thank you for your valuable suggestions! We will incorporate them into the related works section of our future manuscript.

---

Q1. (A) How to ensure the sum of the backward probability on a state is $1$, and (B) the provided codebase "PBP.train_proxy" seems change the sum of log_pb_actions, so the total backward flows will change.

We would like to clarify that (A) is trivial. When we implement the backward policy using softmax, i.e., $\sum_{s\in\text{parent}(s')}P_B(s|s')=1$, the summation of the backward probability on a state satisfies $\sum_{\tau\in\mathcal{T}(x)}P_B(\tau|x)=\sum_{(s_0\rightarrow\cdots\rightarrow s_T)\in\mathcal{T}(x)} {\prod_{t=0}^{T-1}P_B(s_t |s_{t+1})=1}$, by iterating the law of total probability over entire trajectories. Note that we do not constrain $\sum_{\tau\in\mathcal{B}(x)}P_B(\tau|x)$ for observed trjajectories $\tau \in \mathcal{B}(x)$ to be equal to one, but maximize it.

For (B), we would like to clarify that the sum of log_pb_actions corresponds $\log P_B(\tau|x)=\sum_{t=0}^{T-1} \log P_B(s_t|s_{t+1})$ for the given trajectory. The change of this does not affect the total amount of backward flow, i.e, $R(x)\sum_{\tau \in \mathcal{T}(x)}P_B(\tau|x)$, as $\sum_{\tau \in \mathcal{T}(x)}P_B(\tau|x)=1$ is always guaranteed over the entire trajectories.

---

Q2. This paper includes MIS. Can you include more difficult graph combinatorial optimization problems from [1], such as maximum cut?

Indeed, we previously tried other graph combinatorial optimization problems from [1], e.g., the maximum cut problem, but could not reproduce the official results even when using the official implementation. For example, the official score for the maximum cut problem is around $700$, but running their implementation yields a score of $2000$ during the initial training round. To alleviate your concerns, we report the result of PBP-GFN applied to the maximum cut problem in Figure D(c) of our rebuttal PDF.

---

[1] Let the Flows Tell: Solving Graph Combinatorial Problems with GFlowNets, NeurIPS 2023

[2] Order-Preserving GFlowNets, ICLR 2024

[3] Generative Flow Networks as Entropy-Regularized RL, AISTATS 2024

Dear reviewer WPBt,

We are happy to hear that our efforts have addressed your concerns! We also appreciate your insightful comments on our works.

Dear reviewer CTvM,

We express our deep appreciation for your time and insightful comments. In what follows, we address your comments one by one.

---

W1. One can mitigate under-exploitation using a reward-prioritized replay buffer. Adding this as a baseline will be helpful.

We clarify that our experiments on the bag and RNA sequence have already incorporated the reward-prioritized buffer into all baselines and our method (Appendix B). Since the pessimistic backward policy and the reward-prioritized buffer are orthogonal, they are not directly comparable and one can combine them to train GFlowNets.

Nevertheless, to further address your comments, we also considered PBP-GFN without a reward-prioritized buffer and compared it with baselines using a reward-prioritized buffer. We present results in Figure C(b) of our rebuttal PDF. One can observe that the pessimistic backward policy (1) yields similar performance improvements compared to the reward-prioritized buffer, and (2) further improves their performance when combined with it.

---

W2. As an exploitation method, at least one experiment with a larger state-space could be useful, e.g., larger hyper-grid.

We first clarify that our molecule generation environment considers a sufficiently large state space sized up to $10^{16}$ [1]. To further address your suggestion about a larger hyper-grid, we conducted additional experiments on $40\times 40 \times 40 \times 40$ hyper-grid. To the best of our knowledge, this is larger than any hyper-grid experiment conducted in the literature. We present the results in Figure D(b) of our rebuttal PDF. One can observe that our method still shows superior results compared to considered baselines.

---

Q1. What are the hyperparameters for GAFN?

For GAFN, we searched for the coefficient $\alpha$ of intrinsic rewards within $\{1 \mathrm{e-}1, 1 \mathrm{e-}2, 1 \mathrm{e-}3\}$. We designed the random network to have the same architecture as the policy network, but with an output dimension of one, and used a learning rate of $1 \mathrm{e-}3$ for this network.

---

Q2. In a large state space, PBP-GFN may cause $P_F(x)\approx 0$ when $x$ necessitates an action $j$ but PBP-GFN have made probability of $j$ approximately $0$. Curious to hear what you think about this and whether you've done experiments in large-scale environments.

We think that such a potential reduction in the exploration of unobserved objects is natural due to the exploration-exploitation trade-off. As PBP-GFN enhances the exploitation, this may reduce exploration for the unobserved objects in the large state space (discussed in Limitation section). However, we would like to clarify that one can simply relax this issue by reducing the learning rate for the pessimistic backward policy or incorporating an exploration-focused off-policy sampling method to observe $x$ with $P_F(x)\approx 0$.

Furthermore, it is worth noting that our method has already shown good performance in a large state space, e.g., molecule generation sized up to $10^{16}$. This implies that our method is still effective in environments with large state space, as exploitation is also significant for them.

---

[1] Trajectory balance: Improved credit assignment in GFlowNets, NeurIPS 2022

Dear reviewer CTvM,

Thanks you for your response. We appreciate your insightful and constructive feedback for improving our paper in many aspects.

Additionally, we would like to emphasize that we have already empirically analyzed the reduction of exploration (as an exploitation method) in large state spaces by measuring the diversity of high-score objects (Figure 7(c)). However, we observed no particular reduction in practice. In our future manuscript, we will also incorporate an analysis of the case where our PBP-GFN may reduce exploration (Figure B of rebuttal PDF) and discuss mitigation strategies with contents from (u41F-W4,5). We hope that this addresses your concerns.

Dear reviewer smvU,

We express our deep appreciation for your time and insightful comments. In what follows, we address your comments one by one.

---

W1. Does the pessimistic training objective affect the original assumption of GFlowNets training objective?

Our pessimistic training objective does not affect the original assumption of GFlowNet objectives, e.g., DB, TB, and subTB. The assumption of them, i.e., flow matching over entire trajectories $\tau \in \mathcal{T}$ constructs target Boltzmann distribution, is valid for any design of backward policy, i.e., degree of freedom [1,2]. Our pessimistic training objective only modifies this backward policy within the GFlowNet objectives.

---

W2. Did you observe any instability during training after the model had seen a sufficient number of samples?

In our experimental setup, we observed no particular instability after the model had seen a sufficient number of samples.

---

Q1. How do you estimate Equation (5) in practice?

In practice, we estimate the gradients of Equation (5) using the stochastic gradients computed with mini-batch randomly sampled from the buffer $\mathcal{B}$, as described in Algorithm 1. We will update our future manuscript to better reflect this point.

---

Q2. What's the meaning of $N$ in Algorithm 1, and why does pessimistic training require multi-round gradient updates with $N$?

As you mentioned, $N$ is a hyperparameter that specifies the number of update rounds for training the pessimistic backward policy. We require this as we use stochastic gradients to minimize Equation (5), which involves multi-round updates over multiple mini-batches.

---

[1] GFlowNet Foundations, JMLR 24

[2] Trajectory balance: Improved credit assignment in GFlowNets, NeurIPS 2022

Dear reviewer smvU,

We also appreciate your insightful comments. Thank you again for your time and effort for improving our paper!

Dear reviewer u41F,

We express our deep appreciation for your time and insightful comments. In what follows, we address your comments one by one.

---

W1. The paper lacks a strong theoretical analysis to support claims.

We agree that our paper lacks a strong theoretical analysis since we mainly focus on empirical performance improvements. We note that a strong theoretical analysis would be challenging (though valuable) since it requires thinking about the optimization landscape of GFlowNets, where no theoretical results have been made. Hence, we chose to provide insights in Appendix A by analyzing our PBP-GFN under strong assumptions.

---

W2. Compared to existing backward policies [1,2,3], this work (A) does not present a significant conceptual departure and (B) lacks a detailed comparison.

We respectfully disagree with (A). Unlike existing backward policies that focus on under-exploration or credit assignment issues, PBP-GFN is designed to tackle a new under-exploitation problem stemming from the unobserved backward flow.

Next, to resolve (B), we will incorporate the following detailed comparisons with the existing backward policies in our future manuscript.

• While uniform backward policy [1] and MaxEnt backward policy [3] assign a fixed probability to the backward transition for enhancing exploration, our pessimistic backward policy learns the probability of the backward transition for enhancing exploitation.
• While conventional backward policy [1] and sub-structure backward policy [2] may enhance the exploitation by learning the backward flow to align with the forward flow or to improve the credit assignments, they do not directly reduce the unobserved backward flow and do not resolve the under-exploitation stemming from that.

---

W3. Current metrics are insufficient to capture overall quality and diversity. Downstream task-specific metrics would strengthen the paper's claims.

We would like to clarify that we have already incorporated downstream task-specific metrics following prior studies [1,3,4]. We consider the Tanimoto similarity and edit distance to measure the diversity of molecules and RNA sequences, respectively.

To further address your comments on the overall sample quality, we provide the relative mean error [2] which measures the distance between the mean values of the empirical generative distribution and the target Boltzmann distribution. We present the results in Figure A of our rebuttal PDF. One can see that our method shows superior performance.

---

W4. PBP-GFN may reduce exploration in domains with significant uncertainty or where trajectories are not representative of the target distribution. A deeper analysis and empirical evaluation of this are recommended.

To address your comments, we consider a scenario where the observed trajectories are not representative of the target distribution. In this domain, an unobserved high-reward trajectory may largely overlap with an observed low-reward trajectory. Then, to explore the high-reward trajectory, one should assign a relatively high probability to the low-reward trajectory, i.e., the opposite of the case requiring exploitation.

We examplify and analyze this scenario in Figure B of our rebuttal PDF, which (1) illustrates how pessimistic training may reduce exploration by enhancing the exploitation of observed high-reward trajectories and (2) provides an empirical evaluation of the exploration. One can observe that PBP-GFN may reduce the exploration in considered settings.

Despite the potential reduction of exploration, we would like to clarify that our method is still effective as exploitation is significant in most environments. As discussed in Limitation section, there is no free lunch in the exploitation-exploration trade-off. One can futher control the trade-off by interpolating PBP-GFN with explorative GFNs, e.g., MaxEnt, which can be an interesting future work direction.

---

W5. PBP-GFN can amplify biases in initially observed trajectories, hindering the discovery of novel objects, but the paper does not address this or mitigation strategies.

As you mentioned, our method may struggle to discover novel objects when heavily biased towards initially observed trajectories. However, we would like to clarify that such failure cases are rare in practice, as demonstrated in extensive experiments.

Furthermore, to mitigate the bias towards initially observed trajectories, one can reduce the learning rate of the pessimistic backward policy in the initial training rounds. Additionally, incorporating exploration-focused sampling, e.g., a noisy policy, can address this issue. We will add a discussion about this potential risk and mitigation strategies in our future manuscript.

---

W6. The paper lacks a comparison with other exploitation techniques, e.g., local search or reward-prioritized buffer.

First, we clarify that local search and reward-prioritized buffers are sampling methods for off-policy training, that are orthogonal to our pessimistic backward policy, i.e., the methods are not directly comparable. One can combine both approaches to improve performance further. Note that we have already used the reward-prioritized buffer to implement our method and baselines (Appendix B).

Nevertheless, to address your comments, we verify the effectiveness of PBP-GFN by comparing or combining the pessimistic backward policy with local search and reward-prioritized buffer. We present the results in Figure C of our rebuttal PDF. One can observe that our method (1) shows similar performance compared to other techniques and (2) consistently improves the performance when combined with them.

---

[1] Trajectory balance: Improved credit assignment in GFlowNets, NeurIPS 2022

[2] Towards understanding and improving GFlowNet training, ICML 2023

[3] Maximum entropy GFlowNets with soft Q-learning, AISTATS 2024

[4] Local search GFlowNets, ICLR 2024