Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: The paper proposes a Deep RL approach called Auto-Deferring Policy (ADP) to learning a policy for constructing solutions for the Maximum Independent Set (MIS) problem. Rather than constructing a solution one variable per episode step, the policy can make decisions about multiple variables per step, as well as defer decisions to later steps. At each step the MIS constraints of a valid solution are checked and decisions that violate the constraints are reverted, and any additional decisions that are automatically implied by the decisions so far and the MIS constraints are taken. The policy and value function are parameterized as a graph convolutional network to make use of the graph structure of the problem. A diversity regularizer that encourages the policy to generate diverse final solutions is used for training. Results show that the approach is able to match the objective value of the state-of-the-art solvers on several datasets, and is able to outperform S2V-DQN on several datasets when neither approach is trained on them.

Pros:
- Extensive experiments have been done on several datasets, both synthetic and real. The ablation and generalization experiments are particularly valuable for getting insight into the performance of the algorithm.
- Comparison to CPLEX and ReduMIS strengthens the results.
- The paper is reasonably well-written and easy to follow. Figures 2 and 3 are especially useful for quickly understanding key ideas.

Cons:
- The update and clean-up phases inject significant domain knowledge about MIS into the policy. At a high level the idea is similar to unit propagation in Boolean Satisfiability (SAT) solvers or domain propagation in Mixed Integer Programming (MIP) solvers, i.e., the hard constraints of the problem can be used to make decisions in the search for a solution. Both SAT and MIP solvers have been shown to rely on it to significantly improve their search. Improvements over S2V-DQN could be due to this extra built-in domain knowledge, rather than any improvements related to learning. For a fairer comparison, either this knowledge should be removed from ADP as an additional ablation study, or it should somehow be given to S2V-DQN as well. Without such a comparison, it is not clear that the improvements are really due to the new ideas like auto-deferring, diversity regularizer, etc.
- A comparison to Li, Chen, and Koltun, NeurIPS’18 is needed since they have shown strong results for MIS and they have made the code available online. Although their approach is supervised learning, it would still be useful to assess an RL approach’s performance relative to SL.


Additional comments:
- It is not clear what encourages the policy to defer decisions, rather than making all the {0,1} decisions for all variables in one step or a small number of steps. Does this behaviour of the policy arise naturally via training, or does some regularization need to be applied to ensure that the policy doesn’t prematurely fix all variables? For example, as a way to avoid/reduce variance in the reward signal, the policy may learn to fix all variables in just one step -- does this issue arise?

- The abstract says "The reported performance of our generic DRL scheme is also comparable with that of the state-of-the-art solvers specialized for MIS, e.g., ADP outperforms them for some graphs with millions of vertices." Can you please point out the specific results in the paper that this sentence is referring to?

- Comparison to CPLEX:  The paper mentions that “we observe that our algorithm outperforms the CPLEX solver on ER-(100, 200) and ER-(400, 500) datasets, while consuming a smaller amount of time”, and “It is remarkable to observe that ADP outperforms the CPLEX solver on both datasets under reasonably limited time.” Note that CPLEX not only optimizes the objective, but also proves a bound on the objective, while ADP only does the former. So this is not a fair comparison. A fairer comparison would be to set CPLEX hyperparameters to give higher priority to optimizing the objective and then measure the time CPLEX took to first reach a particular objective value rather than the time to “solve” an instance. It can be the case that a given objective value is achieved quickly but then proving a bound requires much longer. Also there is no mention of the optimality gap used as a stopping criterion for CPLEX.

- One potential advantage of making one decision per step is that the credit assignment problem may be simpler compared to making many decisions simultaneously. It would be insightful to explore this tradeoff in more detail.

- The acronym ADP is somewhat well-known in the optimization community as Approximate Dynamic Programming (http://adp.princeton.edu/), so it would be helpful to use a different one.
review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: The paper introduces auto-deferring policies (ADPs) for deep reinforcement learning (RL). ADPs automatically stretching or shrinking their decision process, in particular, deciding whether to finalize the value of each vertex at the current stage or defer to determine it at later stages. ADPs are evaluated on maximum independent set problems. 

The paper is in principle well written and structured. Some statements of the paper appear a little bit too strong. For instance, saying that deep RL approaches "can automatically learn the design of a good solver without using any sophisticated knowledge or hand-crafted heuristic specialized for the target problem" is misleading as thee designer of the RL setup is putting a lot of knowledge into the design. Likewise the statement "without any human guidance" is not true, at least at the current stage. It would be great to acknowledge this by softening this statement.  

The basic idea is also fine, learning to expand or not nodes in the current fringe of the combinatorial solver. However, being an informed outsider, I would like to understand more why encoding NP-hard problem using an (discrete, finite) MDP, which is rather efficient to solve, is a good idea. Moreover, while the focus on MIS is justified in the paper, showing the (potential) benfit on other tasks such as TSP is useful to convince the reader that ADPs apply across different problem classes. Without, it is not clear whether ADPs work fine on other problem classes (even if one may expect that this is the case). 

Anyhow, the main idea of implementing two independent agents/networks to implement a reward signal that rewards deviation is interesting. Moreover, the experimental results show that the approach works. It actually manages to be on par with ReduMIS. However, it does not really improve upon this well-known heuristic. Hence some experiments across different problems would really be beneficial. Without, it is just interesting to see that RL can also come up with good heuristics but the existing heuristic already works pretty well.

To sum up, a very nice idea that shows promise but experiments on other problems is missing for a complete picture. Also some statements should be soften. 
review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: This paper aims at solving graph-based combinatorial optimization problems using a new paradigm for Deep Reinforcement Learning. In contrast with standard Markov Decision Processes used for combinatorial DRL, the authors advocate the use of “deferred” MDPs capturing more complex actions (which can choose a subset of nodes), and more sophisticated transitions, which combine an update phase together with a cleanup phase. For the DRL architecture, an Actor-Critic framework is trained using a proximal policy optimization approach. The paper specifically focuses on the Maximum Independent Set (MIS) problem. Comparative results on various instances reveal that this approach clearly outperforms the S2V-DQN algorithm and is competitive with some usual combinatorial solvers (CPLEX, ReduMIS).

The overall approach is interesting and the experimental results look promising, but it is quite difficult to accept the paper in its current state due to the following reasons:

(a) Though the paper is comprehensible, it is littered with spelling mistakes (just take the first sentence: problem -> problems). For the camera-ready version, it would be nice to use a spell/grammar checker.

(b) The authors focus on the MIS problem, but in the introduction, they claim that their approach can be applied to “any” combinatorial optimization task. Well, that is a bit of an overstatement, due to the immense variety of NP-hard optimization tasks! On the one hand, the MIS problem is already taking an important place in many areas of computer science, and I would suggest concentrating on this task - by changing the title and the summary of the paper, and by just pointing out in the conclusion that the present DRL approach might be applicable to other problems. On the other hand, if the authors are convinced that their DRL approach is generic, then the paper should include other well-known APX-hard problems such as, for example, Min Feedback Node Set, Min Balanced Cut, or Min Set Cover. 

(c) The paper is missing a related-work section. To this point, the MIS problem should be presented in more detail with some theoretical results about its approximability (to within a linear factor, as shown by Boppana and Halldorsson, 1992), and its fixed-parameter tractability (it is W[1]-hard). From an algorithmic viewpoint, the ReduMIS technique is mentioned, but there are many other heuristic approaches and kernelization methods. Notably, OnlineMIS (Dahlum et. al. ESA’16) is orders of magnitude faster than ReduMIS on various large instances. Furthermore, the kernelization technique developed by Chang et. al. (SIGMOD’17) and its parallel version (Hespe et. al., JEA’19) is known to be much more efficient than the kernelization algorithm (VC-Solver) suggested in ReduMIS. Besides heuristic algorithms, very little is said about deep learning approaches for solving MIS. To this point, a more detailed presentation of  Dai et. al.’s approach  (NIPS-17) would be relevant, by explaining the similarities and differences with your approach. Finally, nothing is said about the recent deep architecture proposed by Li et. al. (NIPS’18) for solving MIS. Though they adopt a supervised learning approach, their GCN architecture shares strong similarities with the Actor-Critic framework in the present paper.

(d) The deep auto-deferring policy, presented in Section 3 looks interesting, but it is quite unclear. The main idea lies in deferred MDPs, for which the size of the action space is in $\Omega(3^N)$ because any subset of nodes can be chosen at each state. For such huge MDPs, it is not clear that we can converge to a stable policy in polynomial time. Furthermore, the authors are mixing Actor-Critic (using a graph convolution net) and Proximal Policy Optimization, together with diversification rewards, which makes the overall framework unintelligible. A graphical representation for explaining this complex framework would be welcome. Furthermore, I don’t see how the notion of diversification reward is implemented in the PPO approach for training the agent.

(e) In the experiments, some competitors are missing. As mentioned above, ReduMIS is nowadays dominated by more efficient kernelization/heuristic techniques for solving MIS. I would suggest to instead use OnlineMIS. Moreover, the choice of S2V-DQN is relevant as an RL competitor, but it would be interesting to also use the GCN architecture (Li et. al., NIPS’18) as a supervised competitor. Finally, the SMT solver Z3 is known to be quite efficient for MIS instances (as already observed by Li et. al.), and a comparison with it would indicate whether ADP is competitive (or not) with the best generic solvers.





review_title: Official Blind Review #3

Meta-review: This paper proposes a new way to formulate the design of the deep reinforcement learning that automatically shrinks or expands decision processes.

The paper is borderline and all reviewers appreciate the paper and gives thorough reviews. However, it not completely convince that it is ready publication. 

Rejection is recommended. This can become a nice paper for next conference by taking feedback into account. 
Decision: Reject