Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes a new Tree MDP theory and formalizes the branching problem as a Tree MDP problem.
Under this new formulation, the resulting algorithm benefits sample efficiency and credit assignment.
strengths_and_weaknesses: 
This paper proposes a novel Tree MDP theory, which is well fitted for the branching problem.
The new tree MDP formulation has an obvious advantage over the existing MDP formulation.

However, the paper has some basic theoretical flaws.

My major concern is how could the method be generalized to the test environment? In other words, does there exists an optimal policy that can map the MIP problem into an action?

Assumption 4.2 is strong to me. The paper has offered two conditions in Proposition 4.4 and 4.5.  

However, in P 4.4, if the optimal value is provided, the problem is reduced to another easier problem with equality constraint (is this true?).
In P 4.5, the algorithms can be limited to a very limited scope. 
questions: 
Questions:
My major concern is how could the method be generalized to the test environment? In other words, does there exists an optimal policy that can map the MIP problem into an action?

Although the authors have discussed the limitations in Section 4.4, I think this is the fundamental point about the method, as it is the key to the soundness of the method. I think the paper should discuss more on that.

Some related questions are as follows:

1. What's the architecture of policy \pi_\theta in your implementation? 
2. In line 190, the state is embedded as MILP_i, GUB_i. How to embed a MILP_i? This is a critical problem for generalizing the policy for testing.

Some points are not clear to me:

1. It is not clear to me why a state (MILP_i, GUB_i) can carry enough information to unroll a vanilla B&B algorithm.
2. For a B&B tree in Figure 1, if h is the current state, then it expands from h. After several iterations, is that possible that the policy will still expand d or c or g? 
limitations:
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper proposes a tree MDP formulation for learning to branch in MILP branch-and-bound algorithms. A policy gradient algorithm for solving MILP tree MDPs is proposed. Conditions for the correctness of the algorithm are derived. The paper compares the tree MDP formulation with the vanilla RL formulation as well as a strong baseline (default SCIP) on 5 benchmark problem sets. The main empirical result shows that the tree MDP formulation outperforms the vanilla RL formulation but does not outperform SCIP in 4 out of 5 problems. Similar results are observed for the transfer learning experiments.

--------

UPDATE: I thank the authors for their detailed responses. After reading the other reviews and the responses, I'm a bit more positively inclined towards the paper although the computational performance remains a bit of an issue for me. I've upgraded my score to a Weak Accept.
strengths_and_weaknesses: Strengths
  + There appear to be a number of novel algorithmic contributions (tree MDP, using tree MDPs to encode B&B trees for MILPs, policy gradient algorithm for tree MDPs).
  + The proposed approach seems well-motivated, intuitively clear with correctness guarantees for ObjLim and and DFS (although I didn't check these carefully). Combined with the novelty, this makes the paper interesting in itself.
  + The paper is tackling a problem of significant practical importance (B&B, MILPs) and improvements here would have a large impact.
  + The paper is clearly written and the proposed ideas and experiments are easy to follow.

Weaknesses
  - The empirical results don't show improved performance over the baseline in 4 out of 5 cases. In the case where it does well (Multiple Knapsack), there is no deeper analysis. Overall, the experimental section provides limited insight into the empirical characteristics of tMDP compared to SCIP.
  - It's unclear if the tree MDP formulation can be used in other applications. The paper does not place the tree MDP formulation into the broader (and large) body of work on MDPs. As a result, it becomes difficult to assess the impact of the algorithmic contributions. (This is reflected in my score for presentation and contribution.)
  - The baseline (SCIP branching rule) is not described and the description strong branching is very brief. Coupled with the above, it becomes difficult to place the proposed ideas into the existing body of knowledge.
questions: 1. How novel is the tree MDP formulation?
  - What, if any, relationship, does tMDP have to a recursively-optimal hierarchical RL algorithm like MAXQ [Dietterich99])?

2. Does the tree MDP formulation have other applications besides B&B trees for MILPs?

3. Why does tMDP outperform SCIP default on Multiple Knapsack? Is it possible to characterize how the branching rule learned in tMDP is overcoming the poor relaxation (assuming that's the root cause)? Can the presence / absence of the poor relaxation be verified experimentally?
limitations: There is a discussion on the limitations and social impact in the checklist (but not the main paper). The authors could consider moving it to the main paper.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The main contribution of this paper is a new type of augmented MDP formulation called a “tree MDP”, which is motivated by the “learning to branch” problem in mixed-integer linear programming (MILP). The intuition is to convert the default MDP formulation, which we can think of to be defined over subtrees, into a simpler formulation that is defined over nodes instead. The authors then show computational experiments on a set of benchmarks, showing that the new MDP formulation is more amenable for RL.
strengths_and_weaknesses: Strengths: I found the tree MDP idea used in the paper to be novel, creative, and directly targets the motivating problem without extraneous features and believe that this is a valuable contribution to the literature on applying RL to MILP.

Weaknesses: The ideas in the paper took me some time to properly digest. I believe (nearly) all of the information needed for the reader to digest is there, but think that the paper could make this process easier on the reader. Please see the questions below for specific queries.
questions: Questions:
[Side-by-side comparison] It would be nice to have a side-by-side comparison between the temporal MDP formulation and the tree-MDP formulation, where the states, actions, reward, and definition of episode are compared.
[Requirement of optimal solutions] In Section 3.2, it is mentioned that one of the drawbacks of the standard approach is that “...require to run episodes to completion, that is, to solve MILP instances to optimality, which leads to very long episodes even for moderately hard instances.” However, based on my understanding, the ObjLim version also requires this so it would be nice to properly contextualize some of this (e.g., “with a certain assumption, we can get rid of this requirement”). For the side-by-side comparison mentioned in the point above, it would also be good to mention which assumptions are needed.
[Deterministic MDP formulation] As I was reading through Section 4.1, I was a little thrown off by what is meant by p_ch^- and p_ch^+ since I expected them to be deterministic. It is later specified that the MDP is indeed deterministic (line 215). I wonder if it would be clearer to define a tree MDP only for the deterministic case, rather than in full generality. Is there any point that we need a stochastic tree MDP?
[Other applications of tree MDP] Related to the above, can the authors point to other applications where a tree MDP might be useful? If so, this would be a good reason to present the general setup of a tree MDP.
[Exponentially sized episodes and more difficult policy gradient computation] The paper emphasizes that the states and rewards for a tree MDP are localized to the specific nodes. It would be good to also emphasize that the trade-off here is that each episode is now a tree and therefore can blow up in size -- this trade-off now makes the policy gradient computation more difficult, since it requires a sum over all nodes. If I misdiagnosed the drawback, please correct me, but my concern here is that a cursory read might suggest to a reader that all aspects are simplified compared to before.
[Temporal RL algorithms] In a policy gradient setting, I can see that a tree MDP can be used because the entire episode is run and then (s, a, G) are extracted. Could tree MDPs be used with algorithms like Q-learning that make stronger use of the temporal MDP setup? It is not clear to me that they could because in order to compute an immediate reward, one would need to wait for both child states to be evaluated. Some clarity / discussion on this would be nice!
[Capitalized states and actions] In line page 5, line 182, the states and actions are capitalized -- is this a typo or does it have some significance?
[Figure 1] In Figure 1, the dotted lines are not explained (although I realized that they mean the node was pruned). It would be good to clarify. 
[GNN] What exactly is the state fed to the policy for each of the different algorithms? I was confused by the statement that “same features and architecture” for the GNN are used, but I thought that the states for the MDP / tree MDP approaches are quite different.
[Computational results] What does 1804.6 +/- 17% mean? Is the 17% defined to be 1804.6 +/ 0.17*1804.6? Why do we use geometric mean here? Would the results be different if sample mean were used?
limitations: They have to some extent, but I have also asked for a few more points in the Questions section above.
review_title: null

Meta-review: metareview: The paper studies the MILP problem by providing a tree MDP framework for a more suitable formulation of the branching problem. 
The reviewers believe that this approach is relevant and novel. While in the first round of the review, the reviewers had identified a number of concerns such as the applicability of the tree MDP, concerns about the comparison of baselines, and presentation clarities. The authors have addressed these issues in a satisfactory way in the rebuttal phase. All the reviewers unanimously agree to accept the paper.
confidence: Certain
Decision: Accept