Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a novel combination of policy gradient and local search algorithms for the traveling salesman problems (TSP). The main idea is to apply local search to tours generated by policy rollout and compute policy gradients using the (potentially) improved tour from local search. In addition to the algorithmic contribution, this paper also presents a collection of preprocessing steps to ensure problem instance features are equivalent. Empirical studies are provided on random TSP instances as well as those in TSPLIB. Finally, ablation studies show the importance for each component of the proposed algorithm.
main_review: Originality: Two contributions are original. The first one is algorithmic, i.e., including local search in the training loop of policy gradient. The second is engineering, i.e., applying equivariant preprocessing at each step instead of only once at the beginning. With these two novelties, I think this paper clears the bar for originality.

Quality: Overall this paper is of good quality. I have several questions on the technical details:
1. Could the authors provide a more rigorous derivation for the smoothed policy gradient formula (Equation 8). I did read section B in the Appendix but it jumped from Equation 17, which is the normal policy gradient, to Equation 8 without much explanation. Specifically, is Equation 8 an unbiased gradient estimator for the objective $J^{+}(\theta)$?

A second question on the gradient computation is about the baseline, which is the value of the rollout tour from the policy. Does subtracting this baseline still yield an unbiased gradient estimator?

2. For the empirical studies, can the authors comment on how many random seeds are used to obtain the RL results and what are the variances among different random seed runs?

3. I also noticed that the compared methods are different for random TSP instances and TSPLIB instances. Can the authors provide an explanation? 

Clarity: This paper is well-written and easy to understand. Good job!

Significance: Since I have some important questions regarding the technical contributions, I will need to see the authors’ response in order to have a more informed evaluation of the significance of the paper. In its current state, I think the significance is not enough because of some (potential) technical issues and empirical baseline choices. 

summary_of_the_review: My current recommendation for the paper is marginally below the acceptance threshold. I like the novel ideas in the paper and I admire the thoroughness to include lots of baselines in the random TSP instances comparison. However, there are some unclear points in the algorithmic details. And for the more realistic TSPLIB instances, the number of baselines is much smaller. These two points left me some doubts about the correctness and the significance of the paper.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes a series of techniques and a new model to learn to solve the TSP using RL. First, a number of preprocessing steps are presented in order to transform a TSP instance into a standardized form. Then, a new encoder-decoder architecture is proposed, based on GNN, MLP and attention modules. The authors propose a modification of the policy gradient algorithms for training by replacing the value of the policy-generated solution by its value after applying a local search heuristic, and use the original value as a baseline. Finally they use a curriculum learning approach to increase the difficulty of the instances seen during training, the difficulty here being represented by increasing the size of the instances, within a given interval. Experimental results are presented on standard synthetic and realistic TSP instances of size up to 1000 nodes. 

main_review: **Strengths**
1. The paper is clear and well-written 
2. The proposed preprocessing pipeline is well-motivated and extends nicely previous approaches, in particular by reapplying the preprocessing at each step of the solution construction. It could be leveraged by other learning-based method for solving the TSP.
3. The approach has excellent experimental results:
    * Performance close to (reps. better than) reported state-of-the-art learning-based methods on synthetic (resp. realistic) TSP instances with up to 1000 nodes
    * Good generalisation: one model trained with a range of small instance sizes (up to 50 nodes) is able to generalise to unseen and much larger TSP instances (up to 1000).
    * The ablation study is useful to show the impact of the different components of the approach 


**Weaknesses** 
1. Missing references to related works, which impacts the novelty claims:
    * “To the best of our knowledge, no other work uses curriculum learning for designing an RL-based solver for TSP.” See reference [1] below.
    * The authors claim that (to the best of their knowledge) they are the first to update the encoding of the state to take into account the removal of the visited nodes. This has been explored in (at least in) [2].
2. The proposed approach is presented as a novel approach that exploits “equivariance” but it seems to me that it mostly exploits the properties of the TSP (indeed invariance of the solution to certain transformations of the coordinates) to preprocess the instances. Then the only equivariance that is exploited by the model is with respect to the node ordering, by using a GNN, which is a pretty standard choice of architecture (see e.g. cited [Joshi et al 2019], [Fu et al 2020]). 
3. Overall, the proposed approach is quite specific to the TSP (the preprocessing, the local search and the architecture), it is not straightforward how much of it could be exploited for solving other CO problems. 
4. Some imprecisions/missing information, see Questions.

[1] Lisicki et al. "Evaluating Curriculum Learning Strategies in Neural Combinatorial Optimization." Workshop on Learning Meets Combinatorial Algorithms @ NeurIPS 2020 


[2] Peng et al, A Deep Reinforcement Learning Algorithm Using Dynamic Attention Model for Vehicle Routing Problems. International Symposium on Intelligence Computation and Applications. 2019

**Questions**
1. The form of the policy gradient in equation (8) could be interpreted as the standard policy gradient with as baseline the value of the solution after applying local search. Since the log probabilities correspond to the model’s output solution and not the improved one by local search. Can you comment if this interpretation is correct or not?
2. Given the form of the scores in (9), as normal distributions with mean e the index of the current epoch, when (if) e becomes much bigger than 50 during training, the probability of sampling graphs of size 50 or 10 will be quite close, right? Is it intended? What is the number of epochs range?
3. What is the impact on training time of adding the local search, updating the encodings of all nodes and the preprocessing?
4. Table 1: The results for GCN* are different (a bit worse) from what is reported in the paper [Joshi et al 2019b]. Why is there a difference and why not use the beam-search version of their method the gives better results for running times similar to the proposed eMAGIC?
5. In general, what is the motivation behind the chosen baselines? Versus more recent approaches such as [3]? Why are the baselines not the same in Tables 1-2 and 3? Why not include Concorde and LKH results in Table 3?
6. Table 2: what is the difference between GPN^*5 and GPN^5?
7. Table 3: 
    * what are the running times? this is key to be able to compare the different methods.
    * why are the results of Furthest insertion and OR tools not reported for instances with 400-1002 nodes?


[3] Kwon et al, POMO: Policy Optimization with Multiple Optima for Reinforcement Learning, NeurIPS 2020



**Additional feedback**

Minor typos, mathematical inconsistencies and suggestions
* Introduction:  “equivariance for e” etc —> “e for equivariance” (and same for the others) would be a more standard acronym definition
* Sec 3: “this RL problem corresponds to a repeated N-horizon sequential decision-making problem.” —> repeated (N-t)-horizon ?
* Sec 4.1: “and any coordinates x after preprocessing by $\tilde{x}$” —> missing bold
* Sec 4.2
    * Should \tilde{x}_{\sigma(t-1)} be replaced by \tilde{x}_{\sigma(t)} in the definition of the vector $x$ at $\sigma(n)$? (As in the definition for $\sigma(1)$)
    * The MLP encodes the information about visited cities —>  about the first visited city?
    * As a GNN, it is invariant with respect to .. —> equivariant 
* Sec 5: It seems the sign of the gradient in equation (8) is inconsistent with what is presented in Appendix B
* Sec 6
    * …not being to solve
    * Tables 1 and 2: 
        * the model from [Kool et al 2019] could be called AM instead of GAT for clarity 
        * Putting the best optimality gap in bold would be helpful 
    * …in the their papers



summary_of_the_review: I would vote for reject. My main concern is about the applicability of the proposed contributions beyond the TSP. Clearly the proposed approach is great for the TSP, but it is also somewhat hand-crafted for it (see weaknesses). To me the significance of a TSP-specific learning technique is limited — unless it clearly outperforms specialised TSP solvers such as Concorde or LKH, which is not claimed here. The ultimate goal of learning-based heuristics for combinatorial problems is to replace the handcrafted problem-specific techniques by end-to-end ones. Proving the relevance of the contributions for solving other CO problems would make the paper much stronger.


--------
### Update after rebuttal 

I have appreciated the high quality of the authors rebuttal. My concerns and questions were properly addressed, in particular regarding
* the explanation of the proposed smoothed gradient, 
* the novelty with respect to previous works,
* and the applicability of the proposed contributions beyond the TSP.

Overall, I think the paper provides a set of well-motivated contributions that lead to an RL-based TSP heuristic with a significant improvement in generalisation performance, compared to current “similar” methods. Some of the proposed techniques could be adapted to other CO problems/ML-based CO heuristics. Therefore I believe this paper can be interesting for the NCO community to participate in addressing the well-recognized problem of generalization of ML-based CO solvers.

I am happy to revise my score from 5 (marginally below acceptance threshold) to 8 (accept good paper).
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper introduces a deep RL approach combined with an equivariant model (to handle Euclidean symmetry) and local search heuristics (to improve a tour) to solve traveling salesman problems (TSP), in particular focusing on the generalizability of large-scale instances. The model consists of a graph neural network (GNN), a multi-layer perceptron (MLP), and an attention mechanism. In the training part, this model involves smoothed policy gradient, and stochastic curriculum learning to speed up the training and make the policy more generalizable. The experiments results show that the proposed approach significantly outperforms most learning-based solvers on large-scale randomly generated TSP and realistic TSP.
main_review: Strengths:
1. According to the experiment results, we can see that the proposed algorithm has better generalizability on large-scale TSP and realistic TSP than most learning-based algorithms.

2. Authors propose an equivariant model to handle the symmetry of the combinatorial structures, which has some novelty. 

3. Authors provide detailed experiments and evaluations of different methods and problem instances. 

Weakness:
1. Compared with the learning-based algorithm [1] in TSP 200, 500, 1000, the proposed algorithm has longer computational time and larger gaps. Meanwhile, compared with the state-of-art OR solver LKH3, the proposed algorithm seems to only have a very marginal advantage: TSP200 (LKH: 2.0m, eMAGIC(S): 2.4m); TSP500 (LKH: 11m, eMACGIC(S): 9.7m); TSP1000 (LKH3: 38m, eMACGIC(S): 27m). I would encourage the authors to show more evidence to prove that your model has some empirical improvement.

2. In the conclusion section, the authors claim that 'We demonstrated its effectiveness both on random and realistic instances, which shows that our model can reach state-of-the-art performance.' However, based on table 1 and table 2, it looks like both LKH3 and [1] have better performance than the proposed model. I would expect the authors to provide some details about this claim.

[1] Zhang-Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize a small pre-trained model to arbitrarily large TSP instances. In AAAI, 2021.
summary_of_the_review: Technically, the proposed model uses a standard RL framework with GNN and attention as encoder and decoder. The authors introduce an equivariant model to capture the combinatorial structures of the TSP, which has some novelty and improves the overall performance, but the ablation study does not show that this model provides very significant added value. 

Empirically, the proposed model can outperform most learning-based algorithms on large-size TSP but still can not beat the state-of-the-art learning-based algorithm [1] both in computational time and objective values. Meanwhile, compared with the state-of-art OR solver LKH3, the proposed algorithm does not have enough advantage in terms of computational time.

Therefore, my decision is weak reject. 

[1] Zhang-Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize a small pre-trained model to arbitrarily large TSP instances. In AAAI, 2021.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper employs equivariance properties and local search heuristics to derive a deep learning model capable of generalising to TSP instances of different sizes. The model constructs a tour, one city at a time, by learning a distribution (policy) over unvisited cities which is optimised via REINFORCE. The solution is further refined with a combination of different local search heuristics, and policy gradients are computed with respect to the final improved solution to smooth the loss landscape. The equivariance in TSP is mostly exploited during preprocessing steps—where rotation, translation and reflection operations are applied to the coordinates of each city—but is preserved by the model architecture which consists of a graph neural network and attention mechanisms. The model is trained with stochastic curriculum learning only on small TSP instances ($\leq 50$ cities) but is shown to have competitive performance on problems with up to 1000 cities.
main_review: ### Strengths
- The use of equivariance properties in deep learning models for TSP is promising and, to the best of my knowledge, new.
- The proposed method show competitive results, generalising to TSP instances of different sizes, which is an important and useful trait that is relatively rare in deep learning approaches to combinatorial optimisation.
- The paper is well written and easy to follow. The experimental details are well explained in the appendix and the authors promised to release their code upon publication, so I see no reproducibility issues.

### Weaknesses
- The main contribution of the paper seems to be the use equivariance properties in the TSP, while other aspects of the model are mainly effective tweaks of existing ideas. In particular, the idea to interleave reinforcement learning with traditional combinatorial optimisation heuristics is not entirely new. A similar approach has already been explored in [1].
- Most if not all of the design choices in the paper are very much tailored for the TSP, so I am not confident the approach is *naturally* extendable to other combinatorial optimisation problems as the authors claim. Such an extension would require a whole other set of equivariance properties, local search heuristics, feature engineering tricks and neural architectures, so it is not even clear what aspects of the method the authors deem transferable to other problems.

### Minor issues
- If I understood it correctly the ablation with respect to the combined local search only considers its influence during training time, and all results include a local search step. It would be interesting to see the gap between the quality of the tour output by the deep learning model and the one refined by local search heuristics.
- In page 3, it reads "A state $s_N$ contains the coordinates of the last unvisited city and those of the first and last visited cities". Should it not be "unvisited cities" instead of "last unvisited city"?

[1] Cai, Qingpeng, et al. "Reinforcement learning driven heuristic optimization." arXiv preprint arXiv:1906.06639 (2019).
summary_of_the_review: The paper proposes an effective deep learning model to tackle generalisation in the TSP. While the ideas of the paper are not all novel and somewhat restricted to the TSP, the authors do a great job at integrating previous work on deep learning for combinatorial optimisation into an effective model capable to generalise across problems of different sizes, which is an important challenge in the field. In particular, the use of equivariance properties and the ablation study in the paper should be quite insightful for future work on deep learning for combinatorial optimisation problems.
review_title: null

Meta-review: The paper discusses new RL algorithms for solving large. TSP instances. The algorithm is novel and the problem is important however certain technical questions regarding the soundness of the algorithm were raised. Furthermore, it seems that despite much larger computational time, the algorithm provides only very moderate gains over previous baselines. Finally, it is not clear how the proposed methods (e.g. equivariance) can be applied outside of the TSP problem scope. Thus the concern is the limited impact of the method on the field.

The authors addressed some of the concerns of the reviewers in the rebuttal however it is still not clear:

(1) how the presented mechanism can be applied for other combinatorial problems beyond TSP and therefore how useful it can be for the machine learning community,

(2) how novel the paper is (the use of equivariance is as direct as in the regular graph neural network setup).

Furthermore, the experiments show that the deep learning approach to TSP is still not competitive with standard non-machine baselines. Thus it is not clear whether the proposed algorithm is a right approach to solve this problem, even though it beats other deep learning techniques. The paper is very well written though and the presented method is definitely of value to the research community working on the TSP. Therefore it seems that at this point the paper is more suited for one of the mathematical journals on combinatorics and graph theory.
Decision: Reject