TreeDQN: Sample-Efficient Off-Policy Reinforcement Learning for Combinatorial Optimization

First, we would like to mention that our method is off-policy RL, not offline RL, as you mentioned. The offline RL learns from the offline data, i.e., it does not interact with the environment and tries to learn an optimal policy only from a fixed dataset. The off-policy RL interacts with the environment, it stores all the acquired data in the replay buffer and uses it to learn a policy. In contrast, on-policy RL also requires interaction with the environment but does not store the interaction data and is much more sample inefficient when compared to the off-policy RL methods.

Weakness 1

Thank you for bringing it up. As the Related Work section mentions, the FMCTS method regresses the Q-function to the sampled return (i.e., cumulative discounted reward) obtained in one episode. The TreeDQN method uses the Bellman operator, so we do not need to store the policy-dependent sampled returns; we just store the rewards that do not depend on the policy. The implementation details are available in our Alg. 1 (lines 258 - 262).

Weakness 2

Unfortunately, this is not possible directly since, in the Tree MDP, each node can have multiple child nodes. If we define the state space as the set of all sub-MILPs, the state space will become extremely large. The idea of reinforcement learning is similar to dynamic programming when you can decompose the task into smaller subtasks.

Weakness 3

We apologize for the inconvenience. Fig. 1 starts with 50 updates of the neural network weights, as denoted on the X-axis. Before the first update, FMCTS and TreeDQN, with similar neural network initialization, will produce similar variable selection heuristics and, hence, similar B&B trees.

Weakness 4

Fig. 1 illustrates the tree size on the evaluation dataset during the training. We do not plot the SCIP method here since we want to present the convergence speed of different reinforcement learning methods.

Weakness 5

Thank you for noticing that! We fixed this issue.

Question 1

We prove the results about the Bellman operator as theoretical motivation for our TreeDQN method. Due to the contraction property, we can use the Bellman operator to learn a Q-function in our TreeDQN method. Learning the Q-function with the Bellman operator is more theoretically correct than regressing the Q-function to cumulative returns obtained by older versions of the variable selection policy.

Question 2

The TreeDQN, FMCTS, and tmdp+DFS use similar neural network architecture (see Section 5, lines 307 - 310). All three methods differ in how the training data is acquired and used to train the neural network. FMCTS stores the sampled returns (cumulative discounted rewards) and uses them to regress the Q-function (see sec. 3.3 lines 160 - 164). tmdp+DFS only uses the most recent integration data to perform a gradient update using the REINFORCE-based method (see sec. 3.3 lines 164 - 174). TreeDQN stores the rewards (not sampled returns) and uses the Bellman operator to learn the Q-function (see sec. 4).

Question 3

See the answer to the weakness above.

Question 4

See the answer to the weakness above.

Dear Authors, thank you for answering some of my questions.

Indeed, It is a typo I understood that you were using DQN which is off-policy. Apologies for this.

Unfortunately, I am not convinced about your rebuttal.

Unfortunately, this is not possible directly since, in the Tree MDP, each node can have multiple child nodes. If we define the state space as the set of all sub-MILPs, the state space will become extremely large. The idea of reinforcement learning is similar to dynamic programming when you can decompose the task into smaller subtasks.

Thank you, for explaining what is dynamic programming and what is reinforcement learning. To me it is not a problem to define this state-space of all sub-MILPs with set notation. Then from a practical perspective you will not store all the possible states in memory but you will just implement the transition kernel of the MDP (the step() function in the gymnasium framework).

We do not plot the SCIP method here since we want to present the convergence speed of different reinforcement learning methods.

Isn't it exactly what Etheve et. al. 2020 do in their Figure 2? I find the fact that you refuse to add number of nodes of SCIP or CPLX on your plots suspicious. I also noticed that you use 'FMCTS' everywhere in your text to refer to Etheve et. al. 2020 but the actual name of the algorithm is 'FMSTS' if I am not mistaken

You did not answer the key question: are you sure TreeDQN is actually learning? As I mentioned in my review, the learning curves of TreeDQN are very flat. Could you produce a plot isolating its learning curve (do Figure 1 with only TreeDQN) please?

In the current state I cannot recommend acceptance of your work. I lowered my score until you convinced me that TreeDQN can actually learn B&B trees that are close in size to CPLX' or SCIP'.

Thank you

Weakness 1

We apologize for the inconvenience. Certainly, the value function is policy-dependent; the index $\pi$ was skipped for brevity. We will return it back, so the updated version would be:

$V_{\pi} (s_t) =$ $r(s_t, a_t, s_{t+1}) + p^+V_{\pi}(s^{+}_{t+1}) +$

$p^{−}V_{\pi}(s^{-}_{t+1})$

However, we cann ot agree that the value function shouldn’t depend on the node selection strategy. The value function predicts the expected tree size under the fixed variable selection policy. The node selection policy also influences the resulting size of the tree, thereby influencing the value function. The work [Scavuzzo et al., 2022] also considers a fixed node selection policy. They use a DFS node selection policy in their tmdp+DFS method.

Weakness 2

When we sample training examples from the replay buffer we want the value function to converge to the optimal value function. We can relax the required contraction property of the Bellman operator to the contraction in mean, which with many training examples, would converge our value function to the optimal value function.

Weakness 3

We agree that the construction property of the Bellman operator does not lead to the contraction of the whole method, which includes a value approximator (graph neural network). In our paper, we never stated that the contraction in mean is the only necessary and sufficient condition to guarantee the convergence of our method. We present it here to motivate our approach and highlight that it has more theoretical foundations than, e.g., FMCTS, one of our benchmarks.

Question 1

The value function estimates the expected return with respect to a policy. In the B&B algorithm, the resulting size of the tree depends on the variable selection policy (which is learned by our RL agent) and the node selection policy (we use the SCIP default node selection policy in our experiments). So, different node selection policies change the resulting size of the tree, thereby influencing the value function.

Thanks for the clarifications. However, the theoretical parts still look fragile to me.

1. I don't think the derivation of the contraction property of the Bellman operator is correct. In line 203, since $p^+, p^-$ is state dependent, when taking the maximum, how could one take them out like they are constant.
2. And the authors didn't talk about the optimal Bellman operator either.
3. Also, in Scavuzzo et al., 2022, they have assumption 4.2 under which one can form the problem as a tree MDP. In this work, the authors also formulate the problem as tree MDPs while no assumption is claimed.

Besides, there are many mistakes that one shouldn't make.

1. $p^+, p^-$ should be state-action dependent. One should express this dependency out explicitly
2. In the derivation (line 202-203), $TV-TU$ is a vector, then it suddenly becomes a scalar $p^+V(s^+)+p^-V(s^-)-p^+U(s^+)+p^-U(s^-)$, and when taking the maximum over s, there is even no quantity explicitly dependent on s.
3. The authors say for brevity, they skip the policy when defining the value function. It is not appropriate.

Weakness 1

The SOTA techniques in combinatorial optimization are usually based on task-independent heuristics that could work for many tasks. Meanwhile, in our work, we consider a set of similar MILP tasks, as stated in the Background section. Hence, we benchmark our reinforcement learning method against similar methods that learn variable selection heuristics for a set of similar tasks, such as tmdp+DFS and FMCTS. We also compare SCIP default, strong branching, and imitation learning methods for a more complete evaluation.

Weakness 2

The limit of extrapolation to unseen tasks is a common drawback of all learning-based methods. Despite that, with large training data, ML-based methods can show the SOTA results in many practical applications. In our work, we present the results of transferring learned variable selection policies to more complex transfer tasks in Appendix E. It shows that our TreeDQN method can generalize to more complex tasks while trained on simpler tasks.

Question 1

The contraction property holds under a fixed node selection policy. As the background section mentions, the probability of having left and right children $p^+$, $p^-$ depends on the node selection policy. From the theoretical point of view, other task characteristics, such as average tree depth, do not influence the construction property. However, we use function approximators (graph neural networks) to learn a policy that can limit the method's convergence.

Question 2

Thank you for the important question. We study the choice of the loss function and evaluate TreeDQN with the MSLE and MSE losses in Tab. 2. It shows that our TreeDQN with the MSLE loss function consistently outperforms the competitors. However the learning objectives with MSLE and MSE losses differ. MSLE loss enforces significantly less error on rare large B&B trees (see Fig. 3), hence if the training and evaluation tasks differ and the evaluation tasks produce larger trees than the training ones, the TreeDQN with the MSE loss function could be a better design choice.

Question 3

Thank you for the interesting question. There are different approaches to training a general-purpose heuristic for variable selection:

1. If the tasks are not completely different, it would be possible to train a single agent for all tasks or fine-tune the existing agent to a slightly different B&B task.
2. Another interesting option is the application of progressive neural networks, allowing the agent to extend the learned policy to the different sets of MILP tasks without forgetting the policy for the initial set of tasks.

Rusu, A. A., Rabinowitz, N. C., Desjardins, G., Soyer, H., Kirkpatrick, J., Kavukcuoglu, K., Pascanu, R., & Hadsell, R. (2016). Progressive Neural Networks (Version 4). arXiv. https://doi.org/10.48550/ARXIV.1606.04671

3. The third option that may be the most practical is to train a task classifier and learn separate variable selection policies for each class.