Venue: ICLR 2017 conference

Reviews:

final_score: rating: null
review_content: I am very glad to read "Our model and training code will be made available soon." Thanks for that! My question is: how soon is soon? During the review period? In time for the conference? 
review_title: Code availability

final_score: rating: null
review_content: Is there a comparison that controls for computational cost? e.g. number of cpu cycles?

It doesn't seem fair to compare to search algorithms if one is allowed much more computation than the other.
review_title: Control for computation cost?

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper is methodologically very interesting, and just based on the methodological contribution I would vote for acceptance. However, the paper's sweeping claims of clearly beating existing baselines for TSP have been shown to not hold, with the local search method LK-H solving all the authors' instances to optimality -- in seconds on a CPU, compared to clearly suboptimal results by the authors' method in 25h on a GPU. 

Seeing this clear dominance of the local search method LK-H, I find it irresponsible by the authors that they left Figure 1 as it is -- with the line for "local search" referring to an obviously poor implementation by Google rather than the LK-H local search method that everyone uses. For example, at NIPS, I saw this Figure 1 being used in a talk (I am not sure anymore by whom, but I don't think it was by the authors), the narrative being "RNNs now also clearly perform better than local search". Of course, people would use a figure like that for that purpose, and it is clearly up to the authors to avoid such misconceptions. 

The right course of action upon realizing the real strength of local search with LK-H would've been to make "local search" the same line as "Optimal", showing that the authors' method is still far worse than proper local search. But the authors chose to leave the figure as it was, still suggesting that their method is far better than local search. Probably the authors didn't even think about this, but this of course will mislead the many superficial readers. To people outside of deep learning, this must look like a sensational yet obviously wrong claim. I thus vote for rejection despite the interesting method. 

------------------------

Update after rebuttal and changes:

I'm torn about this paper. 

On the one hand, the paper is very well written and I do think the method is very interesting and promising. I'd even like to try it and improve it in the future. So, from that point of view a clear accept.

On the other hand, the paper was using extremely poor baselines, making the authors' method appear sensationally strong in comparison, and over the course of many iterations of reviewer questions and anonymous feedback, this has come down to the authors' methods being far inferior to the state of the art. That's fine (I expected that all along), but the problem is that the authors don't seem to want this to be true... E.g., they make statements, such as "We find that both greedy approaches are time-efficient and just a few percents worse than optimality."
That statement may be true, but it is very well known in the TSP community that it is typically quite trivial to get to a few percent worse than optimality. What's hard and interesting is to push those last few percent. 
(As a side note: the authors probably don't stop LK-H once it has found the optimal solution, like they do with their own method after finding a local optimum. LK-H is an anytime algorithm, so even if it ran for a day that doesn't mean that it didn't find the optimal solution after milliseconds -- and a solution a few percent suboptimal even faster).

Nevertheless, since the claims have been toned down over the course of the many iterations, I was starting to feel more positive about this paper when just re-reading it. That is, until I got to the section on Knapsack solving. The version of the paper I reviewed was not bad here, as it at least stated two simple heuristics that yield optimal solutions:

"Two simple heuristics are ExpKnap, which employs brand-and-bound with Linear Programming bounds (Pisinger, 1995), and MinKnap, which employs dynamic programming with enumerative bounds (Pisinger, 1997). Exact solutions can also be optained by quantizing the weights to high precisions and then performing dynamic programming with a pseudo-polynomial complexity (Bertsimas & Demir, 2002)." That version then went on to show that these simple heuristics were already optimal, just like their own method.

In a revision between December 11 and 14, however, that paragraph, along with the optimal results of ExpKnap and MinKnap seems to have been dropped, and the authors instead introduced two new poor baseline methods (random search and greedy). This was likely in an effort to find some methods that are not optimal on these very easy instances. I personally find it pointless to present results for random search here, as nobody would use that for TSP. It's like comparing results on MNIST against a decision stump (yes, you'll do better than that, but that is not surprising). The results for greedy are interesting to see. However, dropping the strong results of the simple heuristics ExpKnap and MinKnap (and their entire discussion) appears unresponsible, since the resulting table in the new version of the paper now suggests that the authors' method is better than all baselines. Of course, if all that one is after is a column of bold numbers for ones own approach that's what one can do, but I don't find it responsible to hide the better baselines. Also, why don't the authors try at least the same OR-tools solver from Google that they tried for TSP? It seems to support Knapsack directly: https://developers.google.com/optimization/bin/knapsack

Really, all I'm after is a responsible (and if you wish, humble) presentation of what I believe to be great results that are really promising for the field. The authors just need to make it crystal clear that, as of now, their method is still very far away from the state of the art. And that's OK; you don't typically beat an entire field with one paper. If the authors clearly stated that throughout, I would clearly argue for acceptance ... (Maybe that's not the norm in machine learning, but I don't think you have to beat everything quite yet if your approach is very different and promising -- see DL and ImageNet.)
Concretely, I would recommend that the authors do the following:

- Put the original Figure 1 back in, but dropping the previous poor local search and labelling the line at 1.0 "local search (LK-H) = exact (Concorde)". If the authors would like to, they could also in addition leave the previous poor local search in and label it "Google OR tools (generic local search)" 
- Put the other baselines back into the Knapsack section
- Make sure the wording clearly states throughout that the method is still quite far from the state of the art (it's perfectly fine to strongly state that the direction is very promising).


Overall, this paper has to watch out for not becoming an example of promising too much (some would call it hype-generation) before having state-of-the-art results. (I believe the previous comparison against local search fell into that category, and now the current section on Knapsack does.) I believe that would do a great disservice to our community since it builds up an expectation that the field cannot live up to (and that's a recipe for building up a bubble that has no other chance but burst).

Having said all that, I think the paper can be saved if the authors embrace that they are still far away from the state of the art. I'll be optimistic and trust that they will come around and make the changes I suggested above. Hoping for those changes, since I think the method is a solid step forward, I'm updating my score to a weak accept.
review_title: Promising method, but biased presentation

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper proposes to use RNN and reinforcement learning for solving combinatorial optimization problems. The use of pointer network is interesting as it enables generalization to arbitrary input size. The proposed method also "fintunes" on test examples with active search to achieve better performance.

The proposed method is theoretically interesting as it shows that RNN and RL can be combined to solve combinatorial optimization problems and achieve comparable performance to traditional heuristic based algorithms.

However, the lack of complexity comparison against baselines make it impossible to tell whether the proposed method has any practical value. The matter is further complicated by the fact that the proposed method runs on GPU while baselines run on CPU: it is hard to even come up with a meaningful unit of complexity. Money spent on hardware and electricity per instance may be a viable option.

Further more, the performance comparisons should be taken with a grain of salt as traditional heuristic based algorithms can often give better performance if allowed more computation, which is not controlled across algorithms.


review_title: null

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper applies the pointer network architecture—wherein an attention mechanism is fashioned to point to elements of an input sequence, allowing a decoder to output said elements—in order to solve simple combinatorial optimization problems such as the well-known travelling salesman problem. The network is trained by reinforcement learning using an actor-critic method, with the actor trained using the REINFORCE method, and the critic used to estimate the reward baseline within the REINFORCE objective.

The paper is well written and easy to understand. Its use of a reinforcement learning and attention model framework to learn the structure of the space in which combinatorial problems of variable size can be tackled appears novel. Importantly, it provides an interesting research avenue for revisiting classical neural-based solutions to some combinatorial optimization problems, using recently-developed sequence-to-sequence approaches. As such, I think it merits consideration for the conference.

I have a few comments and some important reservations with the paper:

1) I take exception to the conclusion that the pointer network approach can handle general types of combinatorial optimization problems. The crux of combinatorial problems — for practical applications — lies in the complex constraints that define feasible solutions (e.g. simple generalizations of the TSP that involve time windows, or multiple salesmen). For these problems, it is no longer so simple to exclude possible solutions from the enumeration of the solution by just « striking off » previously-visited instances; in fact, for many of these problems, finding a single feasible solution might in general be a challenge. It would be relevant to include a discussion of whether the Neural Combinatorial Optimization approach could scale to these important classes of problems, and if so, how. My understanding is that this approach, as presented, would be mostly suitable for assignment problems with a very simple constraint structure.

2) The operations research literature is replete with a large number of benchmark problems that have become standard to compare solver quality. For instance, TSPLIB contains a large number of TSP instances (http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/). Likewise, combinatorial optimization problems of various difficulties can be found here: http://www.mat.univie.ac.at/~neum/glopt/test.html. It would greatly add to the paper depth to compare the NCO solution quality on some of these problems. (The CPLEX solver famously evaluates its own progress on such a public library of problem instances.)

3) The paper should explain more clearly the structure of the critic network, and how it performs the mapping from a sequence of cities into a baseline prediction.

4) Suggestions for Algorithm 1:
        Line 5, 6: the notation $i \in [|1,B|]$ is not clear; would $i \in \{1, \ldots, B\}$ be what’s intended?
        Line 7: I’m assuming that this assignment must be done $\forall i$, as in lines 5,6?
        Line 8: $\nabla_\theta$ is used in two different ways, on the LHS and RHS — slight abuse of notation (but we understand the intent).

5) Suggestions for Algorithm 2:
        Line 13: same as for Algorithm 1
        Line 15: use $\times$ instead of $\ast$ to indicate multiplication

review_title: Promising approach to combinatorial optimization

final_score: rating: null
review_content: I believe Christofides' algorithm is the wrong baseline in Figure 1. How would your approach work compared to state-of-the-art heuristic search algorithms, such as Lin Kerningham Helsgaun, or at least compared to something trivial as 2-opt (https://en.wikipedia.org/wiki/2-opt)?

The reference implementation for Lin Kerningham Helsgaun is available here: http://www.akira.ruc.dk/~keld/research/LKH/
2-opt is so basic that there is no reference implementation, but a quick Google search came up with this implementation: http://www.technical-recipes.com/2012/applying-c-implementations-of-2-opt-to-travelling-salesman-problems/

Note that I think it's perfectly OK if those hand-designed algorithms perform way better than your automatic approach, but I believe they are the right thing to compare to. For Concorde, I agree with your previous remark about 50 years of research, but for something as simple and generic as local search with 2-opt this doesn't apply as strongly, since local search can very easily be used in other domains as well.
review_title: Christofides algorithm wrong baseline

final_score: rating: null
review_content: In Table 3, what is the performance for the missing values of RL pretraining with 10.000 batches for Sampling T=1 and T=T*? 

Since performance improved much more from 100 to 1.000 batches for RL pretraining Sampling T=T* than it did for RL pretraining AS (e.g., 5.79->5.71 vs 5.74->5.71 for TSP50), I would expect RL pretraining Sampling T=T* to do better than RL pretraining AS when you use 10.000 samples. This would also change your qualitative conclusion in Table 2 and the overall result of the paper. You seem to glance over this in the text by saying "we sample 1000 batches from a pretrained model, afer which we do not see significant improvement", but seeing the much larger "gradient" from 50, 100, and 1000 batches than for RL pretraining AS, and seeing how key the result is to the final take-away from the paper, I would be far more convinced by just seeing the numbers for 10.000 batches.

Also, what is actually the difference between RL pretraining Sampling T=1 and T=T*? (Maybe I just missed this in the text.)

review_title: Is RL pretraining Sampling T=T* actually better than RL pretraining AS when compared with the same number of 10.000 batches?

Meta-review: This was one of the more controversial submissions to this area, and there was extensive discussion over the merits and contributions of the work. The paper also benefitted from ICLRs open review system as additional researchers chimed in on the paper and the authors resubmitted a draft. The authors did a great job responding and updating the work and responding to criticisms. In the end though, even after these consideration, none of the reviewers strongly supported the work and all of them expressed some reservations. 
 
 Pros:
 - All agree that the work is extremely clear, going as far as saying the work is "very well written" and "easy to understand". 
 - Generally there was a predisposition to support the work for its originality particularly due to its "methodological contributions", and even going so far as a saying it would generally be a natural accept.
 
 Cons:
 - There was a very uncommonly strong backlash to the claims made by the paper, particularly the first draft, but even upon revisions. One reviewer even saying this was an "excellent example of hype-generation far before having state-of-the-art results" and that it was "doing a disservice to our community since it builds up an expectation that the field cannot live up to" . This does not seem to be an isolated reviewer, but a general feeling across the reviews. Another faulting "the toy-ness of the evaluation metric" and the way the comparisons were carried out.
 - A related concern was a feeling that the body of work in operations research was not fully taken account in this work, noting "operations research literature is replete with a large number of benchmark problems that have become standard to compare solver quality". The authors did fix some of these issues, but not to the point that any reviewer stood up for the work.
Decision: Reject