Towards Imitation Learning to Branch for MIP: A Hybrid Reinforcement Learning based Sample Augmentation Approach

Q1: Concerns about the motivation. I think all research that proposes a more complex online RL framework is somewhat incremental, as improving the IL accuracy seems to be the key.

Although Strong Branching is often used for imitation learning and the number of expanding nodes of FSB is significantly less than that of SOTA ML approaches. But it is a rule-based method, which means it tests which of the fractional candidates gives the best progress in the dual bound before actually branching on any of them, which can be viewed as finding the locally best variable to branch on [1]. This means the quality of variable selection in Strong branching can be further improved. So, our method aims to further improve the quality of training samples for imitation learning and jump out from the locally best variable selection strategy of expert rules. As you mentioned, improving the IL accuracy means the exploitation is much higher, but exploration is also important for imitation learning, so how to balance exploitation and exploration also can improve the performance of imitation learning, because in the previous research [2] it has been proven that adding past good experiences can add exploration for imitation learning and may find a potentially better policy than only imitating the expert policy.

Q2: Concerns about the unnecessary complexity of introducing RL and the online updating of the policy during data collection.

To further enhance the efficiency of imitation learning, our approach focuses on the decision of whether to include past good experiences generated by the previously learned policy in the training samples. To achieve this, we employ an online RL agent in each variable selection to make this decision. However, as the past-learned policy iteratively improves, it is crucial to periodically update the online RL agent to ensure more accurate decision-making. Alongside the online RL agent, we also train an offline RL agent as part of our methodology. The offline RL agent serves two purposes: improving the quality of training samples and reducing training time for imitation learning. By leveraging the offline RL agent, we can filter and select higher-quality training samples, leading to improved learning performance.

In terms of experimental results, our method consistently outperforms state-of-the-art learning-based models in synthetic benchmarks, as well as in three ML4CO datasets, as demonstrated in Table 6. Moreover, our approach significantly reduces the training time compared to ML4CO-KIDA, as shown in Table 7 and Table 8. Overall, our approach combines the use of an online RL agent for decision-making and an offline RL agent for sample filtering. Through these enhancements, our method achieves superior branching decisions. Additionally, our approach effectively reduces training time compared to the ML4CO-KIDA method.

Q3: More explanations about the RL-based approach achieving lower IL accuracy while higher e2e performance is required.

As motivation mentioned in Q1, our method focuses on balancing exploitation and exploration to improve imitation learning. The biggest difference between our method and GCNN, and ML4CO-KIDA methods is the training samples, which are combined with input features and labels. For the input feature, all the methods use the bipartite graph feature. For the label, our method's use of the online RL decides a better label in each variable selection, so, our method can generate high-quality training samples rather than only collecting samples from experts. Besides, the offline RL agent also filters higher cumulative reward samples generated from the online RL phase, which not only improves the quality of training samples but also reduces training time for imitation learning. with the iteration, the training sample and learned branching policy will be further optimized. Interestingly, Table 4, Table 5, and Table 6 show that the accuracy of the different methods, namely our method, GCNN, and ML4CO-KIDA, does not correlate with their overall performance.

Q4: Limited improvement compared to ML4CO-KIDA.

As shown in Table 5, as the difficulty of the problem increased, in the easy and medium difficulty, the improvement over ML4CO-KIDA was marginal. But in the hard difficulty, especially in the Maximum Independent Set problem, the improvement becomes more obvious. So, we further evaluate our method in the ML4CO datasets in Table 6, our method's reward dominates the ML4CO-KIDA in all three datasets, especially in anonymous problems, which are inspired by real-world applications of large-scale problems.

Q5: What is the dual bound change when a child node is infeasible?

In this paper, the dual bound change when a child node is infeasible is consistent with your description.

References:

[1] Tobias Achterberg et al. Branching rules revisited. Operations Research Letters, 2005.

[2] Junhyuk Oh et al. Self-imitation learning. In ICML, 2018.

Q1: The ordering of the Tables in the Experiments section is confusing and there are typos and odd sentences in the text.

To make the readers follow the descriptions effectively, we have addressed these issues in the updated PDF file. We assure you that we will provide clearer explanations in the final version of the paper.

Q2: What agent was used to train RL online?

Our methods use the advantage actor-critic to train the online RL agent, which combines the Actor-Critic method and the concept of advantage function. The Actor is responsible for selecting an action based on the current state, while the Critic evaluates the value of this action. The advantage function represents the advantage of an action relative to other actions and can be used to evaluate the value of an action. So, this algorithm can better estimate the value of actions and update parameters based on these values.

Q3: This may be important because the convergence guarantees of RL algorithms are often made in the discounted setting with $\gamma$ < 1.

RL agents have traditionally been tasked with maximizing the value function of a MDP, either in continuous settings, with fixed discount factor $\gamma$ < 1, or in episodic settings, with $\gamma$ = 1 [1]. Because the branching scenario is the episodic setting and the dual bound may remain unchanged for hundreds of steps shown in Figure 2, we set the gamma = 1. Specifically, the value of the gamma does not directly determine the convergence of the model, which is a discount factor used to balance the reward of current and future action in the learning algorithm. But in the branching scenario, with the discount factor $\gamma$ < 1, the reward may have little contribution to the cumulative reward after thousands of branches, which may cause an inaccurate evaluation of the action.

Q4: Confused with the Offline RL agent. To me, offline RL implies learning a policy, why offline RL is described as a filtration mechanism in this paper.

In the context of branching scenarios, learning a branching policy using RL-based methods is less effective compared to imitation learning [2], also presented in Appendix A.5 of our paper. To address this challenge and improve the performance of imitation learning while reducing training time, our method incorporates the use of offline RL agents. This approach aligns with recent research [3], which explores the training of offline RL agents to filter higher cumulative reward training samples.

In Section 3.3 of our paper, we provide a detailed explanation of the implementation. During the training phase, we formulate a constrained optimization problem (Eq.3) that takes input data $\{(O_t, A_t, R_t)\}$ collected from the online RL phase and outputs a real number to fit the cumulative reward. Once the offline RL agent has been trained, it can provide an optimal solution for this constrained optimization problem based on the input state. Concretely, when presented with a new state $\{(O_t, A_t, R_t)\}$, the offline RL agent predicts an optimal cumulative reward $f_{{\theta {{\rm{off}}}}}(O_t, A_t)$. We then utilize this prediction to filter out training samples with actual cumulative rewards below a certain threshold, such as $R_t\geq\ zf{{\theta _{{\rm{off}}}}}(O_t, A_t)$. By employing this approach, we effectively filter out lower cumulative reward samples, focusing on those with higher cumulative rewards.

The integration of offline RL agents in this manner provides a mechanism to enhance the performance of imitation learning, reduce training time, and filter training samples based on higher cumulative rewards.

Q5: The hyperparameter settings in this paper should further explanation.

We will present how to set the hyperparameter in this paper, for the offline RL agent we only train it in the first iteration, because this agent is mainly used to delete the samples with lower cumulative reward, we want to keep it consistent filtration mechanism for the fellow iterations, and the hyperparameter 'z' is set such that the top p% of the data points are selected, so we set it with manual tunings to keep the remaining around 70% of samples, although some research is more radical than ours[3], hyperparameter $\lambda$ is set with 0.02 aims to interpolate the cumulative reward and avoid overfitting. However, for the online RL agents, with the past-learned policy iterative optimized, to generate training samples more accurately, we must update the online RL agent periodically, so, we set the Freq=5, because we observed their relatively higher improvement for the learning branching policy after five iterations.

References:

[1] Pitis, S. (2019). Rethinking the Discount Factor in Reinforcement Learning: A Decision Theoretic Approach. AAAI.

[2] Lara Scavuzzo et al. Learning to branch with tree mdps. NeurIPS, 2022.

[3] Qingyu Qu et al. Yordle: An efficient imitation learning for branch and bound. arXiv preprint arXiv, 2022a.

Q1: The explanation of how the online agent works and how exactly does the online agent decide whether to use the learned policy or expert policy?

We really appreciate your valuable suggestion. Our methods use the advantage actor-critic (A2C) to train the online RL agent, which combines the Actor-Critic method and the concept of advantage function. The Actor is responsible for selecting an action (the action space is discrete, with 2 actions, one to choose the expert and the other to choose the learned policy) based on the current state. At the same time, the Critic evaluates the value of this action. The advantage function represents the advantage of an action relative to other actions. It can be used to evaluate the value of an action. Then use the cumulative reward to measure the quality of the agent's behavior in a given state. So, this algorithm can better estimate the value of actions and update parameters based on these values. When the online RL agent is trained, as shown in Figure 1, in each variable selection, input the state $s_t^O$ to the online RL agent, which will output an action 0 or 1, representing collect the sample generated from past-learned policy or expert policy. It is expected to make better decision-making in each variable selection, generate higher-quality training samples, and achieve effective exploration for imitation learning. This way, the sample generation process can be balanced between exploration and exploitation.

Q2: It is a little unclear to me how much technical novelty is in the design of this framework.

In Appendix A.4, we further discuss the Novelty of Our Data Augmentation Framework for Imitation Learning. Specifically, our framework not only proposed a new approach to enhancing the effectiveness of imitation learning, which is to better balance the exploration and exploitation of imitation learning but also improved the training efficiency of imitation learning, overall, this is a novel data augmentation framework and is technically nontrivial.

We also have undertaken comprehensive tests of our proposed framework. Extensive experiments on different MIP problems show the effectiveness of our method compared with open-source solver SCIP and other competing baselines, even achieving superior performance over the leading commercial solver in some cases. In addition, our method shows superior generalization ability.

Q3: How time-consuming is strong branching compared to your method?

The strong branch is often used for imitation learning because it is a globally effective yet computationally expensive rule. At the beginning of our experiment, we also compared with the strong branch rule, as shown in the table below, we tested the result in the combinatorial auction problem with easy difficulty. However, as the experiment progressed, we found the strong branch was too slow, and it seriously affected the efficiency of testing and its solving time was significantly more than other methods. So we removed the strong branch in our experiment.

Q4: "Offline DRL", which was initially discussed in some earlier papers, You might want to change the writing here to be more accurate.

We really appreciate your valuable suggestion. The "offline DRL" is initially discussed in Fujimoto et al. (2018) [1], we will clarify this in the final version.

Q5: Why there is no highlight on the best-accuracy method for each task?

Upon reviewing the findings presented in Table 4, Table 5, and Table 6, it becomes evident that the accuracy of the different methods, namely our method, GCNN, and ML4CO-KIDA, does not correlate with their overall performance. Therefore, it is inappropriate to single out any specific method as the best-performing one.

Q6: Why is it the case that the proposed method can reduce training time compared to other methods?

As shown in Table 7 and Table 8, For the training time, the offline RL plays a significant role in reducing the training samples, the training sample size of our proposed HRL-Aug reduced by around 30% at each iteration compared with ML4CO-KIDA, which is the reason why our method can reduce training time compared to ML4CO-KIDA. Moreover, our online RL agents operate within a relatively small state-action space, involving only two actions. Hence, despite the general notion that RL agents can be time-consuming to train, our method effectively mitigates this concern by leveraging offline RL and operating within a compact state-action space, resulting in a negligible increase in training time compared to the overall training process.

References:

[1] Fujimoto S , Meger D , Precup D .Off-Policy Deep Reinforcement Learning without Exploration[J]. 2018.