Learning to Branch with Offline Reinforcement Learning

We want to thank Reviewer s5Ux’s careful review and valuable advice. Some of the questions are actually related to the common practice in the existing work, but we will try our best to improve the experimental setting and clarify some descriptions based on your suggestions.

Which variables are the selected ones?

Only the node chosen by the node selection policy is used. The node selection policy is fixed. Thanks for the question and we will make this part clear.

Further, it is not exactly clear whether there is a single model trained and evaluated on all instances, or multiple independent models trained on and evaluated on individual datasets.

We have multiple independent models trained on and evaluated on individual datasets. Actually, the description of the experimental settings exactly follows the descriptions in the previous works, but we will add more clarifications in our final version.

One missing benchmark is the utilization of an off-the-shelf offline RL algorithm

See Table 13 and 14 for the comparison with CQL.

The testing set is also rather small: 10k training instances, 2k validation instances, and 20 test instances is a strange ratio.

This ratio is actually a common practice utilized in existing works. 20 test instances x 5 seeds leading to 100 measurements. We follow your suggestion to expand the number of testing instances to 100 in Table 9 and 10, which leads to 500 measurements. The reason for such a small testing set is due to its time measurement, which could be inaccurate under parallel computing, and we believe this is a common problem in the existing research.

Why only look at the dual bound improvement (alternative: optimality gap between primal and dual)?

First, this is not a weird choice since the dual-integral is also a common metric to evaluate the quality of the branching policy, where only the dual bound is used. Second, dual-bound improvement is used to compute the score in the strong branching, which is empirically proven to be a powerful branching policy. It can somewhat directly reflect the quality of the instant branching decision leading to it while primal-dual gap cannot. Finally, the improvement from the primal bound is highly related to the primal heuristics, and is sometimes hard to fit with the node features.

In Sec 3.2. “In fact, a good action does no harm to policy optimization even if it is an OOD action” – can you please elaborate on this a bit more?

Offline RL treats those actions with a low frequency in the dataset as OOD actions and avoids the query on these actions since the value estimation on these actions is inaccurate due to the lack of samples. However, if we can verify an action is good, for example, it brings a high dual-bound improvement, then we do not have to worry about its inaccurate value estimation. If its value is underestimated, this action will not be chosen by our actor, then there is no difference. If its value is over-estimated, our actor will choose this action, but since we have verified through the dual-bound improvement that it is highly possible to be a good action, it still brings no harm.

We want to thank reviewer pc5v for your questions and constructive suggestions. Here are our responses to all of your comments.

The authors need to clarify the necessity of utilizing offline reinforcement learning.

We have briefly discussed the comparison in the third paragraph in our introduction part, here we will try to further explain why using offline reinforcement learning is meaningful.

1. Training reinforcement learning for branching is super time-consuming [1,2]. It is because interacting with the solver could also be slow (long interaction time) and the BnB tree could be super large when a RL policy is very bad at the beginning. Here we cite the training time from two recent RL for branching papers, We set a maximum of 15,000 epochs and a time limit of six days for training and we left our retro branching agent to train for ≈ 13 days (≈ 500k epochs). In comparison, the offline models can all be trained within hours.

2. Bad performance of current RL methods. The results from the current two papers demonstrate that their performance is still way worse the imitation learning methods. In Table 2 and 3, we have also shown that the RL agent (tMDP) is even worse than RCAC which is trained over sub-optimal or small datasets.

3. There are lots of known problems in training online RL agents for branching, as summarized in [2]. For example, existing RL methods choose the size of the search tree as the reward function, which leads to a sparse reward environment and that is why we propose to use the improvement in the dual-bound as the reward function. A subsequent problem is the credit assignment problem (how to tell which action leads to the good/bad outcomes), which is studied by [1], but the the model performance shows that this problem is still far from being solved.

[1] Lara Scavuzzo, Feng Yang Chen, Didier Chetelat, Maxime Gasse, Andrea Lodi, Neil Yorke-Smith, and Karen Aardal. Learning to branch with tree MDPs. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022.

[2] Christopher W. F. Parsonson, Alexandre Laterre, and Thomas D. Barrett. Reinforcement learning for branch-and-bound optimisation using retrospective trajectories. Proceedings of the AAAI Conference on Artificial Intelligence, 37(4):4061–4069, Jun. 2023.

In Equation 7, when k is small, the distribution of Q-values over the dataset will be centered around -δ, which is unfavorable for training. How do the authors ensure training effectiveness in this scenario?

Thanks for this great question. Actually, we do not directly fit the output of critic network $Q$ to $-\delta$. Note in Equation 8, we only change the output of the target network to $-\delta$. We realize this by first letting the target network output its value, then replace some of those outputs with $-\delta$. The target network needs no training, so it will not be fit to a distribution with values centered around $-\delta$. Then the fitting target of $Q$ in Equation 7 is also not a distribution with values centered around $-\delta$.

I believe that the essence of the method proposed by the authors lies in further refining the dataset, specifically selecting the top-k actions in Gω for Bellman operator operations.

We think there could be some misconceptions here. $G_{\omega}$ is also a neural network rather than a set, so we actually do not do any dataset refining, i.e., filtering out good transitions from the dataset for training. The ranking is conducted on the scores of the $G_{\omega}$, so the top-k actions do not necessarily have to be in the collected dataset, that is, we do not observe the reward for all these top-k actions. But we can still evaluate these transitions with our learned Q-network.

I am curious to know if, after obtaining the top-k actions in Gω, simple imitation learning on these state-action pairs would yield similar results as the current approach. In other words, my question is whether the key to the effectiveness of this algorithm lies in the dataset refinement rather than offline reinforcement learning. I suggest that the authors conduct further ablation experiments to validate this idea.

We believe the most relevant results are in Table 5, since $G_{\omega}$ has already been a neural network, simply imitating $G_{\omega}$ is just a distillation of the model. The better performance of RCAC over $G_{\omega}$ has already demonstrated that the source of improvement is from offline reinforcement learning.

We want to thank the reviewer’s questions, we have actually covered some of them in the paper, here we give more discussions about these points.

The novelty of the proposed method is incremental, as the proposed method is a simple application of offline reinforcement learning methods to branching strategies learning.

RCAC is not just a simple application of one offline RL algorithm to learning to branch. We actually start with the CQL algorithm and gradually modify the offline RL algorithm to the current framework, here we summarize some core technical contributions in our work.

Using a hard constraint (ranking) rather than the soft constraint adopted in many previous offline RL algorithms, such as CQL. This is because branching performance is somewhat sensitive to the branching decisions, a very bad branching decision would cause a huge subsequent BnB tree. Therefore, the offline RL agent should be trained more conservatively and that is why we use ranking as the constraint. Using a weighted cross entropy loss $G_{\omega}$ rather than a standard behavior cloning cross entropy loss. To overcome the over-conservativeness of RCAC, we give more preference to those promising actions when we rank the actions. This is realized through the dual-bound improvement, which is a heuristic adopted in strong branching.

Using the dual-bound improvement as the reward function. As we discuss in section 3.1, compared with the BnB tree size, dual-bound improvement is denser and more flexible to compute, which serves as a better reward function.

We also add the comparison with CQL in Table 13 and 14.

We want to thank Reviewer nNZN for your positive feedback. Please see the responses below for your questions.

A large part of the paper talks about sub-optimality of the FSB policy. For example, this statement "Although FSB generally achieves high-quality branching, it could still become sub-optimal when the linear programming relaxation is uninformative or there exists dual degeneracy" Is there more justified argument for this backed by some evidence?

The potential sub-optimality of Strong Branching has been pointed out in previous RL papers [1]. For example, in the multi-knapsack dataset, Strong Branching behaves clearly worse than RL methods. Even in Table 1, it can be observed that SB is worse than RPB.

why choose the proposed algorithm over any existing offline RL algorithm like CQL[1], IQL etc.?

Using a hard constraint (ranking) rather than the soft constraint adopted in many previous offline RL algorithms, such as CQL. This is because branching performance is somewhat sensitive to the branching decisions, a very bad branching decision would cause a huge subsequent BnB tree. Therefore, the offline RL agent should be trained more conservatively and that is why we use ranking as the constraint.

Please also see Table 13 and 14 for the comparison with CQL in our updated version.

What are connections of equation 6 to reward weighed regression?

Equation 6 can be treated as a coarse-version of the reward weighed regression, since we only use the instant reward rather than the cumulative reward. Using instant rewards does not always make sense in the general RL formulation, but it works here since dual-bound improvement itself can reflect the quality of the branching decisions.

[1] Lara Scavuzzo, Feng Yang Chen, Didier Chetelat, Maxime Gasse, Andrea Lodi, Neil Yorke-Smith, and Karen Aardal. Learning to branch with tree MDPs. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022.

We want to thank Reviewer 9gri for your questions and constructive suggestions on our empirical evaluations. Please see the following responses for your questions.

Lack of Scaling-Generalization Results:

See Table 11 and 12 in our updated version

The paper lacks a thorough comparison with recent advancements in the GGCN framework, particularly the augmented loss function introduced in "Lookback for Learning to Branch".

This paper focuses more on a better imitation of the strong branching, which is a bit different from what we study. Besides, the code for this paper is not public, we will try to ask the authors for the code or reproduce it in the final version.

However, an alternative comparison could involve integrating rewards into the GGCN framework as an additional signal.

Actually, $G_{\omega}$ is trained in the way you suggest. Our result in Table 5 indicates that $G_{\omega}$ has already brought some improvements, but RCAC can further boost the performance. Also, to ensure the reward if informative, we choose the dual-bound rather than the tree size used in previous RL for branching methods.

Comparisons with other RL methods, especially in terms of dataset size and time efficiency, would also be valuable.

We actually discuss it in Section 4.2. Here we cite the training time from two recent RL for branching papers, We set a maximum of 15,000 epochs and a time limit of six days for training [1] and we left our retro branching agent to train for ≈ 13 days (≈ 500k epochs) [2] . In comparison, the offline models can all be trained within hours.

[1] Lara Scavuzzo, Feng Yang Chen, Didier Chetelat, Maxime Gasse, Andrea Lodi, Neil Yorke-Smith, and Karen Aardal. Learning to branch with tree MDPs. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022.

[2] Christopher W. F. Parsonson, Alexandre Laterre, and Thomas D. Barrett. Reinforcement learning for branch-and-bound optimisation using retrospective trajectories. Proceedings of the AAAI Conference on Artificial Intelligence, 37(4):4061–4069, Jun. 2023.

Section 3.3: Should "representation of the B&B tree" be replaced with "representation of the B&B node" for accuracy?

Yes, thanks for the suggestion and we have updated it.

Training Dataset for GGCN (H) and RCAC (H): Are these models trained on the same dataset? Is GGCN (H) trained on a separate dataset collected as specified in the Appendix?

Yes. Please see Section 4.1, the paragraph above Table 1, for more details about the two datasets.

VHB Dataset Transitions: Could the authors clarify what constitutes a 'transition' in this context? Does the transition include (s,a,s’) even when FSB is not employed in VHB, which is 0.05 times? Do you discard any transition? How is it ensured that you explore a wide array of instances before 100K transitions are collected?

Each transition, as defined in section 2.3, includes (s,a,s’, r(s,a)), which corresponds to the current state, current action, next state and the instant reward. It is always the same no matter VHB or SB is used. We do not discard any transition or make any sub-sequence sampling due to our basic assumption that collecting the samples is expensive. So the exploration of diverse instances is not considered in our case.

S Method Training: Is the S method trained with only 5K transitions?

Yes.

Reward Distribution: Could the authors provide details on the distribution of reward values in the dataset, perhaps in the Appendix?

See Figure 4 in our updated version.

Figure 3 Clarity: What is the specific problem family represented in Figure 3?

As the title suggests, it is the CA (combinatorial auction) problem. We change the ranking constraint $k$ and report of performance change of RCAC.

Practicality of H dataset collection: Given that VHB takes longer than FSB (as indicated in column 2), is it still a practical choice since the performance is worse than S?

The answer could also be found in the paragraph we refer to in the response to clarification 2. In short, VHB is used to simulate the scenario where the best available heuristics are sub-optimal. Since on these 4 commonly used datasets, SB has already been strong enough, we use VHB to simulate a sub-optimal policy and evaluate the performance of RCAC. Besides, models also have a better performance when trained on the dataset collected by VHB on the CFL problem, so it could also sometimes become a better choice.

GGCN Expansion: Could the authors clarify the abbreviation GGCN? It seems to be a variation of GCNN (Graph Convolutional Neural Networks) as used in Gasse et al. 2019.

We actually use GGCN to refer to the method used in Gasse et al. 2019. Since GCN or GCNN is more like a model name, which is also adopted in our learning method, to discriminate the learning method name from the model name, we try to use the author name G(asse)GCN to name the method.