Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: This paper tackles the problem of program synthesis in a subset of x86 machine code from input-output examples. First, the paper uses a random code generation policy to generate many programs and executes them with random inputs to obtain I/O and program pairs. Then, the paper trains a model using imitation learning on this dataset, and then transitions to to using policy gradient and Monte Carlo Tree Search methods to train the network.

I thought it was quite cool that the paper generates assembly code, but the set of instructions allowed is quite limited. While the paper seems a bit dismissive about prior work such as Balog et al 2017 that use "query languages", the higher-level primitives found in such languages (like "filter") could also mean that the models involved have to learn higher-level semantics than what this model needs.

Furthermore, the paper only uses two input-output examples to specify the desired behavior, and the accuracy of the model's output is only evaluated on that pair of examples. While the paper discusses in Section 5.2 that it is important to learn general methods to solve a provided task, this evaluation setting prevents . Similar to previous work like Bunel et al 2018, I would encourage the authors to measure how well the generated programs can do on held-out example input-output pairs, to see whether the model could successfully recover the "intended" program; to assist with this, we can also increase the number of input-output pairs used to specify the task. Of course, this would make it probably impossible to recover the "hard" problems from section 4.3, since those require conditional execution.

I think the paper should have cited works such as
- https://arxiv.org/abs/1906.04604
- https://openreview.net/forum?id=H1gfOiAqYm
- https://papers.nips.cc/paper/8107-improving-neural-program-synthesis-with-inferred-execution-traces
which also make use of execution information in order to predict the code. In particular, the first paper in this list also uses tree search methods to generate programs as a sequence of loop and branch-free instructions, so I believe it should be quite similar to this paper at a high level.

Considering the above limitations with the evaluation methodology, and the limited novelty of this work in light of these citations, I vote for weak reject.
review_title: Official Blind Review #2

final_score: rating: 1: Reject
review_content: The authors propose to tackle the problem of neural inductive program synthesis using a combination of REINFORCE, imitation learning, and MCTS. Furthermore, they propose a method for sampling tasks that aims at minimising task correlation when optimizing the policy parameters. They test their method on a set of input-output sequences provided by automatically generated x86 programs, and a small set of manually designed programs.


Given the current state of the manuscript, this is a clear reject. Some of the main issues I notice are:

1. The novelty of the proposed (combined) method is unclear, given that it is a relatively straightforward combination of relatively simple and battle-tested techniques; I don't consider this in general to be a problem, but previous work has explored the problem way more significantly both algorithmically and in modeling terms.

2. The experimental section is entirely composed of non-standard datasets, and - in general - the manuscript lacks almost entirely in critical details regarding how the datasets are generated; e.g. What is the pilot policy? Is there a finite set of IO tasks defined for all the experiments? How were the manual tasks designed? What are the qualitative differences in task dynamics between the two experiment settings?

3. The baselines are extremely basic, especially considering that there are a multitude of papers - some of which are mentioned in sections 1 and 2 - that would provide for some excellent comparison. Furthermore, there's a lack of details about the model setup, hyperparameters, state featurization, and so on.

4. Across the manuscript there seems to be some apparent confusion on whether they are tackling the problem as a multi-task setting, where each IO set is considered to be a separate task, or whether all of these tasks are just instances of a single MDP. Given that the program space is well defined, I would think that modelling the problem as a single task is more appropriate, however the authors seem to have chosen a multi-task approach. However, in such case there's also a lot of previous work on multi-task RL and meta-learning that should have been mentioned and potentially used / compared against. This also affects how sensible their proposed sampling method is (and whether the assumption wrt on-policyness actually is reasonable).

I would encourage the authors to improve the work in the following ways:
- Please include the nitty gritty details about the setup, including dataset, simulator, training and algorithmic hyperparameters, state featurization, etc. - try to make experimental reproduction as easy as possible exclusively based on the manuscript.
- Clarify the setup wrt. point 4 above; ideally formalize the problem statement using MDPs, such that it can be properly reasoned upon.
- Review more closely previous work, and choose a suitable (and possibly recent and as close to SOTA as reasonably possible) baseline, such that the proposed methods can be quantitatively and qualitatively compared.
- Similarly, please attempt to test your method on existing environments and datasets, such that any analysis against previous baselines can be fairly assessed.

review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: [Summary] 
This paper addresses the problem of synthesizing programs (x86 assembly code) from input/output (I/O) pairs. To this end, the paper proposes a framework (AutoAssemblet) that first learns a policy network and a value network using imitation learning (IL) and reinforcement learning (RL) and then leverages Monte Carlo Tree Search (MCTS) to infer programs. The experiments show that AutoAssemblet can synthesize assembly programs from I/O pairs to some extent. Ablation studies suggest the proposed IL and RL guided search is effective.

Significance: are the results significant? 2/5
Novelty: are the problems or approaches novel? 2/5
Evaluation: are claims well-supported by theoretical analysis or experimental results? 4/5
Clarity: is the paper well-organized and clearly written? 4/5

[Strengths]

*clarity*
The overall writing is clear. The authors utilize figures well to illustrate the ideas. Figure 1 clearly shows the proposed pipeline as well as the MCTS process. In general, the notations and formulations are well-explained. 

*technical contribution*
- Optimizing both the imitation learning loss and the reinforcement learning loss yields better performance when more tasks are available and tasks are more difficult.
- Leveraging a learned policy network and value network for improving the efficiency of the MCTS seems effective.

*ablation study*
Ablation studies are comprehensive. The proposed framework first optimizes two losses (IL and RL) and leverages the learned policy network and the value network for improving MCTS. The provided ablation studies help analyze the effectiveness of each of them.

*experimental results*
- All the descriptions of the experiments and the presentations of the results are fairly clear. 
- The results demonstrate the effectiveness of the proposed RL guided MCTS.

[Weaknesses]

*novelty*
Overall, I do not find enough novelty from any aspects while the overall effort of this paper is appreciated. The reasons are as follows.
- This  "self-learning" framework is not entirely novel since it has been proposed in [1], where the model is trained on a large number of programs that were randomly generated and tested on a real-world dataset (FlashFill). 
- The hybrid objective (IL+RL) has been explored in neural program synthesis [2] (a supervised learning model is fine-tuned using RL), learning robot manipulation [3], character control [4], etc.
- Utilizing Monte Carlo Tree Search for program synthesis has been studied in many works. [5] proposes to treat the network outputs as proposals for a sequential Monte Carlo sampling scheme and [6] presents an RL guided Monte Carlo tree search framework. 
- Program synthesis on assembly languages: RISC-V [6], etc.

*related work*
The descriptions of the related work are not comprehensive. While many neural synthesis works [1, 5, 7-10] have explored a wide range of settings for learning to perform program synthesis, they are not mentioned in the paper. I suggest the authors conduct a comprehensive survey on this line of works. 

*baselines*
In my opinion, the baselines (imitation, REINFORCE, MCTS) presented in the paper are far from comprehensive. I believe the following baselines should also be considered:
- As the proposed model optimizes a combination of the IL loss and the RL loss, it would make sense to also evaluate a model optimizing this hybrid loss.
- Search-based program synthesis baseline (i.e. learning guided search vs heuristic search)
- Comparing the proposed framework against some neural induction baselines would confirm the importance and effectiveness of explicitly synthesizing programs instead of directly predicting the outcome/output. This has been shown in [1, 7].

*testing set*
The testing sets are extremely small (with only 50, 40, 40 programs), which makes the results less convincing. Also, how those testing sets were created is not mentioned anywhere in the paper. It only states "we designed a set of human-designed tasks".

*number of given I/O pairs*
It is not mentioned anywhere how the authors split the observed I/O pairs and the assessment I/O pairs such as what has been done in most of the works [1, 2, 7, 8]. While the observed I/O pairs are input to the program synthesis framework, the assessment I/O pairs are used to evaluate the synthesized programs. By doing so, the more observed I/O pairs are given, the more accurate the synthesized programs should be (assuming the model can find programs that fit the observed I/O pairs). 
- The discovery (Figure 2d) in this paper is contradictory to what is mentioned above: the program synthesis accuracy decreases when more I/O pairs are given. I am assuming the authors do not split observed I/O pairs and assessment I/O pairs.
- With the setup where the observed I/O pairs are separated from the assessment I/O pairs, a larger number of K (the number of the observed I/O pairs) should be used so that it is more likely that the program for each task is unique and the evaluation would make more sense.

[1] "RobustFill: Neural Program Learning under Noisy I/O" in ICML 2017
[2] "Leveraging Grammar and Reinforcement Learning for Neural Program Synthesis" in ICLR 2018
[3] "Reinforcement and Imitation Learning for Diverse Visuomotor Skills" in RSS 2018
[4] "DeepMimic: Example-Guided Deep Reinforcement Learning of Physics-Based Character Skills" in SIGGRAPH 2018
[5] "Learning to Infer Graphics Programs from Hand-Drawn Images" in NeurIPS 2018
[6] "Program Synthesis Through Reinforcement Learning Guided Tree Search" arXiv 2018
[7] "Neural Program Synthesis from Diverse Demonstration Videos" in ICML 2019
[8] "Execution-Guided Neural Program Synthesis" in ICLR 2019
[9] "Learning to Describe Scenes with Programs" in ICLR 2019
[10] "Learning to Infer and Execute 3D Shape Programs" in ICLR 2019

===== After rebuttal =====

I appreciate the authors for the revision and for clarifying some points. I am still not entirely convinced by the response and the revision.

First, I mentioned several papers that are related to this work, the authors failed to discuss the difference between this submission and these works. 
- The "self-learning" paradigm is used in [1, 2, 7, 8] but [1, 7] are still not mentioned. If the authors intentionally ignore these works so that they can claim the novelty, it is not acceptable.
- While the proposed hybrid objective is very similar to the one proposed in [2, 3, 4], the revision does not mention this.
- Why [5, 6] that utilizing Monte Carlo Tree Search for program synthesis are still missing from the revision? I believe these works are very relevant to this submission.
- The authors acknowledged that they did not know about [6] that works on program synthesis for an assembly language. Yet, this paper is still missing from the paper.
I spent a lot of time conducting a survey in this field to help the authors to improve this submission and trying to identify the novelty of this submission. However,  the authors just chose to ignore it, which is very disappointing.

Second, many suggestions that I made are just rejected by the authors because they believe it is "not very easy and trivial". Given this self-learning setting, I believe it would be easy to implement some program induction baselines using supervised learning. Or how about search-based program synthesis baselines?

The writing about 50, 40, 40 testing sets is very misleading. I believe all the reviewers just think the testing accuracy was computed using those testing sets.

From my point of view, "program aliasing” does not mean there are not sufficient I/O examples to fully describe a task; Instead, it means there are programs written differently can be semantically the same, which means no matter how many input examples are given, their outputs will always match.

Overall, I believe this submission requires a serious revision and I firmly recommend this paper to be rejected.
review_title: Official Blind Review #3

Meta-review: The authors consider the problem of program induction from input-output pairs.                                                     
They propose an approach based on a combination of imitation learning from                                                         
an auto-curriculum for policy and value functions and alpha-go style tree search.                                                   
It is a applied to inducing assembly programs and compared to ablation                                                             
baselines.                                                                                                                         
                                                                                                                                   
This paper is below acceptance threshold, based on the reviews and my own                                                          
reading.                                                                                                                           
The main points of concern are a lack of novelty (the proposed approach is                                                         
similar to previously published approaches in program synthesis), missing                                                          
references to prior work and a lack of baselines for the experiments.
Decision: Reject