Venue: ICLR 2018 conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper focuses on using RNNs to generate straightline computer programs (ie. code strings) using reinforcement learning.  The basic setup assumes a setting where we do not have access to input/output samples, but instead only have access to a separate reward function for each desired program that indicates how close a predicted program is to the correct one.  This reward function is used to train a separate RNN for each desired program.

The general space of generating straight-line programs of this form has been explored before, and their main contribution is the use of a priorty queue of highest scoring programs during training.  This queue contains the highest scoring programs which have been observed at any point in the training so far, and they consider two different objectives:  (1) the standard policy-gradient objective which tries to maximize the expected reward and (2) a supervised learning objective which tries to maximize the average probability of the top-K samples.  They show that this priority queue algorithm significantly improves the stability of the resulting synthesis procedure such that when synthesis succeeds at all, it succeeds for most of the random seeds used.

This is a nice result, but I did not feel as though their algorithm was sufficently different from the algorithm used by Liang et. al. 2017.  In Liang et. al. they keep around the best observed program for each input sample.  They argue that their work is different from Liang et. al. because they show that they can learn effectively using only objective (2) while completely dropping objective (1).  However I'm quite worried these results only apply in very specific setups.  It seems that if the policy gradient objective is not used, and there are not K different programs which generate the correct output, then the Top-K objective alone will encourage the model to continue to put equal probability on the programs in the Top-K which do not generate an incorrect output.

I also found the setup itself to be poorly motivated.  I was not able to imagine a reasonable setting where we would have access to a reward function of this form without input/output examples.  The paper did not provide any such examples, and in their experiments they implement the proposed reward function by assuming access to a set of input/output examples.  I feel as though the restriction to the reward function in this case makes the problem uncessarily hard, and does not represent an important use-case.  

In addition I had the following more minor concerns:

1.  At the end of section 4.3 the paper is inconsistent about whether the test cases are randomly generated or hand picked, and whether they use 5 test cases for all problems, or sometimes up to 20 test cases.  If they are hand picked (and the number of test cases is hand chosen for each problem), then how dependant are the results on an appropriate choice of test cases?

2.  They argue that they don't need to separate train and test, but I think it is important to be sure that the generated programs work on test cases that are not a part of the reward function.  They say that "almost always" the synthesizer does not overfit, but I would have liked them to be clear about whether their reported results include any cases of overfitting (i.e. did they ensure they the final generate program always generalized)? 

3.  It is worth noting that while their technique succeeds much more consistently than the baseline genetic algorithm, the genetic algorithm actually succeeds at least once, on more tasks (19 vs. 17).  The success rate is probably a good indicator of whether the technique will scale to more complex problems, but I would have prefered to see this in the results, rather than just hoping it will be true (i.e. by including my complicated problems where the genetic algorithm never succeeds).

review_title: Focus on the success

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper presents an algorithm called Priority Queue Training (PQT) for
program synthesis using an RNN where the RNN is trained in presence of a 
reward signal over the desired program outputs. The RNN learns a policy 
that generates a sequence of characters in BF conditioned on a prefix of characters.
The key idea in PQT is to maintain a buffer of top-K programs at each 
gradient update step, and use them to perform additional supervised learning
of the policy to guide the policy towards generating higher reward programs.
PQT is compared against genetic algorithm (GA) and policy gradient (PG) based
approaches on a set of BF benchmarks, where PQT is able to achieve the most 
number of average successes out of 25 runs.

Unlike previous synthesis approaches that use supervision in terms of ground
truth programs or outputs, the presented technique only requires a reward 
function, which is much more general. It is impressive to see that a simple 
technique of using top-K programs to provide additional supervision during 
training can outperform strong GA and PG baselines.

It seems that the PQT approach is dependent on being able to come up with a 
reasonably good initial policy \pi such that the top-K programs in the priority 
queue are reasonable, otherwise the supervised signal might make the RNN policy
worse. How many iterations are needed for PQT to come up with the target programs?
It would be interesting to see the curve that plots the statistics about the 
rewards of the top-K programs in the priority queue over the number of iterations.

Is there also some assumption being made here in terms of the class of programs
that can be learnt using the current scoring function? For example, can the if/then
conditional tasks from the AI Programmer paper be learnt using the presented 
scoring function?

I have several questions regarding the evaluation and comparison metrics.

For the tuning task (remove-char), GA seems to achieve a larger number of
successes (12) compared to PQT (5) and PG+PQT (1). Is it only because the 
NPE is 5M or is there some other reasons for the large gap?

The criterion for success in the evaluation is not a standard one for program
synthesis. Ideally, the success criterion should be whether a technique is able
to find any program that is consistent with the examples. Observing the results
in Table 3, it looks like GA is able to synthesize a program for 3 more benchmarks
(count-char, copy-reverse, and substring) whereas PQT is only able to solve one
more benchmark (cascade) than GA (on which PQT instead seems to overfit).
Is there some insights into how the PQT approach can be made to solve those 
tasks that GA is able to solve?

How do the numbers in Table 3 look like when the NPE is 5M and when NPE is 
larger say 100M?

There are many learnt programs in Table 4 that do not seem to generalize to new 
inputs. How is a learnt program checked to be correct in the results reported 
in Table 3? It seems the current criterion is just to check for correctness on 
a set of 5 to 20 predefined static test cases used during training. For every 
benchmark, it would be good to separately construct a set of held out test cases 
(possibly of larger lengths) to evaluate the generalization correctness of the 
learnt programs. How would the numbers in Table 3 look with such a correctness 
criterion of evaluating on a held-out set?

Are there some insights regarding why programs such as divide-2, dedup or echo-thrice
can not be learnt by PQT or any other approach? The GA approach in the AI programmer 
paper is able to learn multiply-2 and multiply-3 programs that seems comparable to 
the complexity of divide-2 task. Can PQT learn multiply-3 program as well?

review_title: Interesting PQT approach using top-K highest reward programs

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper introduces a method for regularizing the REINFORCE algorithm by keeping around a small set of known high-quality samples as part of the sample set when performing stochastic gradient estimation.

I question the value of program synthesis in a language which is not human-readable. Typically, source code as function representation is desirable because it is human-interpretable. Code written in brainfuck is not  readable by humans. In the related work, a paper by Nachum et al is criticized for providing a sequence of machine instructions, rather than code in a language. Since code in brainfuck is essentially a sequence of pointer arithmetic operations, and does not include any concept of compositionality or modularity of code (e.g. functions or variables), it is not clear what advantage this representation presents. Neither am I particularly convinced by the benchmark of a GA for generating BF code. None of these programs are particularly complex: most of the examples found in table 4 are quite short, over half of them 16 characters or fewer. 500 million evaluations is a lot. There are no program synthesis examples demonstrating types of functions which perform complex tasks involving e.g. recursion, such as sorting operations.

There is also an odd attitude in the writing of this paper, reflected in the excerpt from the first paragraph describing that traditional approaches to program synthesis “… typically do not make use of machine learning and therefore require domain specific knowledge about the programming languages and hand-crafted heuristics to speed up the underlying combinatorial search. To create more generic programming tools without much domain specific knowledge …”. Why is this a goal? What is learned by restricting models to be unaware of obviously available domain-specific knowledge? 

All this said, the priority queue training presented here for reinforcement learning with sparse rewards is interesting, and appears to significantly improve the quality of results from a naive policy gradient approach. It would be nice to provide some sort of analysis of it, even an empirical one. For example, how frequently are the entries in the queue updated? Is this consistent over training time? How was the decision of K=10 reached? Is a separate queue per distributed training instance a choice made for implementation reasons, or because it provides helpful additional “regularization”? While the paper does demonstrate that PQT is helpful on this very particular task, it makes very little effort to investigate *why* it is helpful, or whether it will usefully generalize to other domains.

Some analysis, perhaps even on just a small toy problem, of e.g. the effect of the PQT on the variance of the gradient estimates produced by REINFORCE, would go a long way towards convincing a skeptical reader of the value of this approach. It would also help clarify under what situations one should or should not use this. Any insight into how one should best set the lambda hyperparameters would also be very appreciated.
review_title: The PQT algorithm is nice, but more analysis would be much appreciated. Also, BF is an odd language to target for program synthesis.

Meta-review: This paper introduces a possibly useful new RL idea (though it's a incremental on Liang et al), but the evaluations don't say much about why it works (when it does), and we didn't find the target application convincing.

Decision: Reject