Short version:
In summary, this paper makes strong claims of generalisation and efficiency
but does not seem to provide sufficently strong evidence to back them up, e.g.
it does not perform an asymptotic analysis to support the efficiency claim, it
doesn't show actual program output to allow the evaluation of what is actually
learned and the claim about strong generalisation is based on a very vaguely
described experimental setup.
Longer version below.
Interesting paper. It describes a Reinforcement Learning method to learn
neural network models that imitate the behaviour of agents performing a)
sorting, b) binary search and c) solutions to the NP-complete knapsack
problem. The technique is notable because it learns from program traces also,
not only from input-output pairs. The technique relies on a hard-coded set of
problem-dependent a) input states and b) instruction sets. The latter are what
it sounds like, sets of instructions that form the building blocks of the
learned programs, although in an enhanced version of the technique, functions
are also added to the (less complex?) instructions. Input states basically
include all other information that may be useful to a learner, other than the
instructions and functions from which to build a program. Two different setups
are tested: a) one using the single instruction "swap" (that swaps two
elements) and where the input state includes information of the full list, and
b) one with more instructions and localised information that is reported to
generalise better and be more efficient. The latter setup is also augmented
with "functions" which are stated to be more complex than operations, though
the distinction is rather on the vague side (there is some more information in
an appendix but it's not very helpful, I'm still left wondering why an
"instruction" is qualitatively different to a "function").
The paper is poorly organised and requires long appendices to elucidate all
manner of poorly defined concepts in the main paper. This doesn't help when it
comes time to evaluate the two most striking claims in the paper, namely that
the proposed method(s?) a) show strong generalisation and b) outperform
hand-crafted sorting algorithm quick-sort in sorting lists of numbers.
The first claim is difficult to evaluate because the paper presents results of
sorting lists of variable _size_ but does not say anything clear about list
_contents_. For example, while training lists are chosen to have a random
length in [10,20] and with elements in the same range, testing lists have
their length incrased, but there is no mention of the values of the elements
in those litss and, going by what is described in appendix C, lists can have
duplicate values. In other words, it's possible that the "strong
generalisation" results refer to sorting lists of variable size with the same
unique elements as in the training lists. In that case, the claim of "strong"
genearlisation is not supported.
The second claim is difficult to evaluate for two reasons: a) there is no
example of the training output, i.e. we never get to see what progams,
exactly, the proposed approach is learning; and b) there is no attempt to
asymptotic analysis of the learned models (which would be hard without an
example thereof). Instead, the claim of efficiency seems to rest on two
presmises: a) that sorting programs of O(n log n) time complexity are in the
hypothesis space defined by the input states and instruction sets and
functions for the relevant experimental setup, i.e. the learner could learn
an O(n log n) sorting algorithm; and, b) that the number of training steps
taken by the learning agents in imitation of the teacher agents is in the
ballparck of n log n of the input. In other words, the strongest evidence for
the efficiency claim seems to be a count of instructions (or function) calls
during training. So, this very strong claim is also very poorly supported.