Published as a conference paper at ICLR 2018 LEVERAGING GRAMMAR AND REINFORCEMENT LEARNING FOR NEURAL PROGRAM SYNTHESIS
Program synthesis is the task of automatically generating a program consistent with a specification. Recent years have seen proposal of a number of neural approaches for program synthesis, many of which adopt a sequence generation paradigm similar to neural machine translation, in which sequence-to-sequence models are trained to maximize the likelihood of known reference programs. While achieving impressive results, this strategy has two key limitations. First, it ignores Program Aliasing: the fact that many different programs may satisfy a given specification (especially with incomplete specifications such as a few input-output examples). By maximizing the likelihood of only a single reference program, it penalizes many semantically correct programs, which can adversely affect the synthesizer performance. Second, this strategy overlooks the fact that programs have a strict syntax that can be efficiently checked. To address the first limitation, we perform reinforcement learning on top of a supervised model with an objective that explicitly maximizes the likelihood of generating semantically correct programs. For addressing the second limitation, we introduce a training procedure that directly maximizes the probability of generating syntactically correct programs that fulfill the specification. We show that our contributions lead to improved accuracy of the models, especially in cases where the training data is limited.
The authors consider the task of program synthesis in the Karel DSL. Their innovations are to use reinforcement learning to guide sequential generation of tokes towards a high reward output, incorporate syntax checking into the synthesis procedure to prune syntactically invalid programs. Finally they learn a model that predicts correctness of syntax in absence of a syntax checker. 
While the results in this paper look good, I found many aspects of the exposition difficult to follow. In section 4, the authors define objectives, but do not clearly describe how these objectives are optimized, instead relying on the read to infer from context how REINFORCE and beam search are applied. I was not able to understand whether syntactic corrected is enforce by way of the reward introduced in section 4, or by way of the conditioning introduced in section 5.1. Discussion of the experimental results coould similarly be clearer. The best method very clearly depends on the taks and the amount of available data, but I found it difficult to extract an intuition for which method works best in which setting and why. 
On the whole this seems like a promising paper. That said, I think the authors would need to convincingly address issues of clarity in order for this to appear. 
Specific comments 
- Figure 2 is too small 
- Equation 8 is confusing in that it defines a Monte Carlo estimate of the expected reward, rather than an estimator of the gradient of the expected reward (which is what REINFORCE is). 
- It is not clear the how beam search is carried out. In equation (10) there appear to be two problems. The first is that the index i appears twice (once in i=1..N and once in i \in 1..C), the second is that λ_r refers to an index that does not appear. More generally, beam search is normally an algorithm where at each search depth, the set of candidate paths is pruned according to some heuristic. What is the heuristic here? Is syntax checking used at each step of token generation, or something along these lines? 
 
- What is the value of the learned syntax in section 5.2? Presumaly we need a large corpus of syntax-checked training examples to learn this model, which means that, in practice, we still need to have a syntax-checker available, do we not?