Abstract
We study the problem of learning efficient algorithms that stronglygeneralize in the framework of neural program induction. By carefully designingthe input / output interfaces of the neural model and through imitation, we areable to learn models that produce correct results for arbitrary input sizes,achieving strong generalization. Moreover, by using reinforcement learning, weoptimize for program efficiency metrics, and discover new algorithms thatsurpass the teacher used in imitation. With this, our approach can learn tooutperform custom-written solutions for a variety of problems, as we tested iton sorting, searching in ordered lists and the NP-complete 0/1 knapsackproblem, which sets a notable milestone in the field of Neural ProgramInduction. As highlights, our learned model can perform sorting perfectly onany input data size we tested on, with $O(n log n)$ complexity, whilstoutperforming hand-coded algorithms, including quick sort, in number ofoperations even for list sizes far beyond those seen during training.