Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Deep reinforcement learning (DRL) has recently been applied to variety of optimization problems, outperforming traditional approaches. This paper investigates the application of DRL to the context of routing problems such as the classical travelling salesman problem. The methodology proposed involves two DRL agents: the seeder, which is tasked with generating candidates for the solution that provide a good coverage of the solution space, and the reviser, which is tasked with attaining better solutions based on the reduced solution space provided by the seeder. To generate diverse candidates, the seeder utilizes entropy regularization reward. The authors present experiments indicating that their framework, called learning collaborative policies (LCP) improves over previous DRL frameworks for various routing challenges (e.g., TSP and capacitated vehicle routing).
main_review: Thanks you for submitting to NeurIPS 2021.

The paper is reasonably well written and the results are, overall, clearly explained.

I found the approach presented for addressing routing problems (seeder + reviser) interesting.

I wonder what makes routing problems special? Do you expect the same approach to attain good results in other optimization domains? Or is there something about the structure of TSP and the other routing problems discussed that is of special significance here? I encourage the authors to elaborate on this point.

I think that the paper could also benefit from more discussion of why the approach produces good results. Specifically, the seeder-reviser methodology is somewhat reminiscent of traditional local search via genetic algorithms, simulated annealing, etc., where many random solutions are generated and these are combined in various ways to generate better solutions. I realize that the argument is that the generation of such candidate solutions by the seeder is better because of the entropy regularization reward, and that employing DRL by the reviser somehow helps it generalize better, but I would have appreciated more discussion/investigation of this point.

Post author response:

Thank you for your responses to my concerns. I still view this as a borderline paper but am adjusting my score to 6.
limitations_and_societal_impact: No negative societal impact is expected.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper introduces Learning Collaborative Policies (LCP) for learning to optimize TSP-style routing problems. The goal of this was not to outperform all other optimizers, but to outperform RL optimizers, which are usually less effective than traditional approaches, but also are more scalable to task-variation. This makes this class of optimizers more suitable for real-world problems. LCP uses 2 policies to optimize a TSP: a seeder, and a reviser. The seeder generates many valid but diverse solutions (ensured with an entropy maximization term in the reward). The reviser learns to relax small sections of each seed to create more optimal solutions. Revision is repeated a set number of times and the best solution is given.
main_review: Strengths:

•	Elegant idea.
             - Macro-optimization through learned seeding + micro-optimization through revision.
•	Beat baseline RL algorithms in 3 TSP variants with 20, 50, and 100 nodes.
             - Variants seemed representative (educated guess).
•	Real-world applicability + scalability.
             - Some of these applications are mentioned.
•	Figures are well-made and understandable.
•	Ablation study is good.
•	Reproducibility info including hyperparameters is mentioned and indexed in the appendix. Code will also be provided in the final version.

Weaknesses:
•	Unprofessional writing.
            - Most starkly, “policies” is misspelled in the title.
•	At times, information is not given in an easy-to-understand way.
            - E.G. lines 147 - 152, 284 - 289.
•	Captions of figures do not help elucidate what is going on in the figure. This problem is mitigated by the quality of the figures, but it still makes it much harder to understand the pipeline of LCP and its components. More emphasis on that pipeline would help with the understanding.
•	100 nodes seem like a small maximum test size for TSP problems (though this is an educated guess). Many real-world problems have thousands or tens of thousands of nodes.
•	Increase in optimality is either not very significant, or not presented to highlight its significance. It would be better to put the improvement into perspective.
•	Blank spaces in table 1 are unclear.

Opportunities:

•	It would be good to describe why certain choices were made. For example, why is the REINFORCE algorithm used for training versus something like PPO? I presume it has to do with the attention model paper this one iterates on, but clarification would be good.

•	More real-world uses of the algorithm could be included to better understand the societal impact, including details on how LCP could be integrated well.

The paper lacks a high degree of polish and professionalism, but its formatting (e.g. bolded inline subsubsections) and figures are its saving grace. The tables are also well structured, if a bit cluttered --- values are small and bolding is indistinct. This paper does a good job of giving this information and promises open source-code on publication.

Overall, the paper and its presentation have several problems, but the idea seems elegant and useful. 

limitations_and_societal_impact: Yes. The authors have adequately addressed the limitations and potential negative societal impact of their work
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper addressed the hard routing problems based on a hierarchical strategy consists of two DRL policies called the seeder and reviser. Together with the two policies, to assess the diversity of candidate solutions, the entropy-regularized reward is adopted. The revise divides the tour into subtours and optimizes the length of them. Experimental results suggest that the proposed LCP framework works on TSP, PCTSP, and CVRP instances.
main_review: As the authors mentioned, the proposed LCP framework is not designed to outperform problem-specific solvers (e.g., Concorde for TSP). Therefore, the authors formulate the routing problems as MDP and the task of DRL-policies is to sequentially design a new task (i.e., select one of the unserved tasks). Since the next task should be taken depends on the current status (and implicitly already assigned tasks), the MDP-based approach seems to be reasonable. In addition, the reward-based study covers various problem tasks.

The idea of the seeder (preparing diverse solutions) and revise (updating solutions) is a kind of a traditional approach to solvecombinatorial problems, but the RL-based formulation seems to work efficiently to various problems. Technically the paper seems to be sound but the structure of the paper is a bit hard to follow although the author revised the paper when submission, because the paper covers branches of classes and showed various experimental comparisons (and most of them are included in Appendix).

### Weights for diverse candidate routes

As far as I understand the proposed formulation correctly, the seeder follows a parameterized policy from the previous work [11]. Therefore, the important part of the LCP seems from the entropy-regularized reward to search diverse areas of all solution spaces, which is supported by the reviser part. Although the entropy is hard to compute exactly, a weighted sum of the selected routings is adopted and the weights on the early stage are set to be higher. This weighting mechanism seems to be interesting to generate diverse solutions.  Although this weighting scheme is a hyper-parameter (or hand-crafted setting), the experimental results indicated that the difference of weights does not affect the result too much (e.g., Table 5 of Appendix B). 

My concerns are
- (a) Do fixed parameters in Table 5 (e.g., N of TSP, I=10, T=2, ... ) affect the comparison of the provided results?
- (b) Can we have similar results for real instances? As far as I know, characteristics of random TSP (or other class) instances are hard to tune and in some cases, results are different from those obtained from real instances.
- (c) In Appendix E, the performance of the reviser is evaluated by a kind of ablation test using Drl2-Opt. Did the author evaluate the performance of the seeder? (i.e., some heuristics + reviser) If this kind of comparison is useless for some reason, please clarify it to highlight the advantage of the proposed method (or, for example, Appendix D covers this kind of experiment?).

### Revise

The revision process of candidate seeds is essential for LCP. The key background to design the reviser is solving small routing instances is easy (l = L-2). As noted in Sec.4.2, DRL-2opt searches O(N^2) solution space but the LCP searches O(MK l!). 

- (d) I suspect that LCP with smaller l (i.e., L) could generate worse solutions than Drl2-opt. Is this correct or do the authors investigate the case?
- (e) The authors mentioned only Drl-2Opt in Sec.4.2. Since the proposed LCP could be applied to PCTSP and CVRP, some RL-based solvers (e.g., AM, NLNS) should be mentioned on the viewpoint of search space to highlight the advantage of LCP if possible.

In addition to $l$, the parameter $I$ should be carefully examined in my opinion. For PCTSP and CVRP, relatively small $I$ is used (1, 5), while TSP uses $l=10$ an $45$. Why such small values are used? Please add the concept of these used parameter values if possible.
limitations_and_societal_impact: Solving various classes in a unified manner (or hybrid manner with existing methods) is a promising work in the literature.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes to learn collaborative policies for routing problems. Collaborative policies firstly learn to generate many diversified and primitive solution candidates. Then for each solution candidate, they segment the original problem into several sub-problems. Another neural network model is trained to improve these sub-problems. The improved solutions of the sub-problems can be merged to form a new solution for the original problem.  They teste their methods on the TSP, PCTSP, CVRP problems and achieve the best performance among all the baselines. 
main_review: Originality: 
I think the method is a smart combination of "Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances" Fu et al., "Deep Policy Dynamic Programming for Vehicle Routing Problems" Kool et al and "Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning" Costa et al. However, the related work section mentions these two works but does not discuss the relation to these three works. 

Quality:

The main contribution of this paper is to make the entire pipeline fully deep learning and do not require any label during the training process. The paper uses a neural network model trained with DRL to generate the primitive solutions and proposes an entropy regularizer term to increase the diversity of the solutions.  Previous works typically supervised train a model to predict the importance of each edge and create the sub-problems (solutions). For the improving phase, this paper uses another neural network model trained through DRL to improve the sub-solutions.  While the previous works leverage DP algorithm, MCTS, or require labels.

The experiment results look good to me. The method beats all the fully neural baselines with reasonable time.

Clarity:

The paper has some important points that I am confused about.

1. How did you generate the sub-problems (segments) of a candidate solution? I assume it is fully random and make sure the points you selected are connected? I think this step is vital in the entire process but it is not explained.
2. For training the revision policy, how did you generate the training instances? It is exactly the same as the one for seeder policy?

Significance:

The method is smart to leverage the previous ideas in fully deep learning and no label required way. 

Questions:

1. I think one interesting ablation study can be: what if you use a supervised trained model to generate the segments/sub-problems like what they did in "Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances". I am wondering how the entropy regularize help compared with a supervised method.

2. For the TSP problems, the size of the sub-problems is 10 vertices. In this case, why a revision model is required since you can compute the optimal solution very fast for only 10 vertices? What're the results then? What if you increase the size of the sub-problems (which can potentially be generalized to huge TSP problems).

limitations_and_societal_impact: For the limitations, the authors do not talk about will the method scale to high problems, e.g., TSP-10000. My feeling is that the seeder policy may be not good enough if the size of the sub-problems is increased a lot. 

I don't think this work has some bad societal impact.
review_title: null

Meta-review: This paper proposes Learning Collaborative Policies (LCP) for learning to optimize  routing problems. LCP is  a hierarchical strategy that consists of two RL policies called the seeder and reviser. The seeder generates many valid but diverse solutions (using an entropy maximization term in the reward). The reviser learns to relax parts of  the  seed to create more optimal solutions. This process is repeated and the best solution is given. The authors apply the approach to different routing problems (TSP, PCTSP, CVRP problems) and achieve the best performance among all the baselines. There was some discussion, the reviewers felt the authors made a great effort to address the concerns raised by them, which led to the increase of the score by one of the reviewers, and overall the consensus was that the paper was ok, above the threshold.
Decision: Accept (Poster)