Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: In this paper, the authors propose a new class of programs they call programming puzzles. The authors argue that this class of programs is ideal for helping learn AI systems to reason. The second contribution of the paper is an adaptive method of puzzle generation inspired by GAN-like generation that can generate a diverse and difficult set of programs. The paper shows that the generated puzzles are reasonably difficult to solve (using the time to solve as a measure of difficulty) and reasonably diverse. 

I found the paper well-written and easy to understand. The methodology to generate programs is convincing. I am not sure time to solve is the best way to measure the complexity of the program, but it seems a reasonable proxy. Did the authors study if the program length is correlated to the time to execute? If the correlation holds, then can complex programs not be created by simply having a bias towards longer programs? That would be a strong baseline to compare against. 

I may have missed something, but I understand that only the Guided Solver is trainable. If that is the case, then why do we see increase in solving time for other solvers (Table 1). In only the case of the Guided solver can the generator adaptively increase the complexity of the programs. 

Overall, I feel that the paper puts forth an interesting class of programs. But there are some gaps in the evaluation and the baselines. I am also not sure how this class of programs can help advance artificial reasoning. 

Feedback:
- The authors should provide more references to the solvers used in Section 5. 
- The paper ends abruptly. A summary/conclusion would be useful. 

I am not an expert in this area, and I am willing to revise my recommendation if the authors can address these issues.

review_title: Official Blind Review #4

final_score: rating: 3: Weak Reject
review_content: This paper proposes a trainable 'puzzle' program synthesizer that outputs a program f with a specific syntax. These 'puzzles' are structured as boolean programs, and a program solver solves the puzzle by finding an input x such that f(x) = True.  The authors motivate this task by making a case that puzzles of this sort are a good domain for teaching computers how to program.

The paper is fairly clear overall. There is some repetition in the early parts, so this could be restructured a bit, but these are minor points. A more significant restructuring however, is that this work would benefit from the related work being present the beginning of the work. Since this work is so similar in many ways to previous work I think the overall clarity of the paper would be improved, and the contributions clearer, if the work was better situated with respect to related work.

The experiments demonstrate that the trainable puzzle generator is able to produce harder (i.e. takes longer time to solve) puzzles than a random or probabilistic generator of the same grammar. While this does show that the program generator is learning something useful, these results are insufficient to show the utility of this approach in any real context. It seems the most interesting solver to assess is a trainable solver. Yet only 1 of the 4  solvers they assess is trainable. I know the authors make a point that they are not putting forward any new solver algorithms. That ok, however, taking existing trainable solvers and assessing how they perform with this guided puzzle generation vs. some other puzzle generation approach is a critical empirical study. Furthermore, it would be helpful to have more discussion of the baseline methods of generating puzzles. When the trainable puzzle solver was originally proposed, how was it trained? Where did the  data come from? How does that compare to this approach. I am not very familiar with this literature, and I imagine this paper would be of interest to folks outside the program synthesis space, so it would be very helpful to better explain this (also we note about related work). There are several additional empirical analysis that could be added to improve this work. For example, for the trainable solver, a plot of (training time) vs (time to solve puzzle) would be interesting. Beyond looking at training time, does a solver trained with the guided puzzle generator end up being a 'better' solver in some way? Are the resulting puzzles harder but still being solved? Is there a way of quantifying the 'hardness' of a puzzle? Perhaps a proxy like size? Then it would be cool to plot (training time) vs (approx puzzle hardness) to demonstrate that . the puzzle generator is really developing a reasonable curriculum.

Finally, there is a bunch of related work that I think is missing. Again, I'm not super familiar with this work, but I think there is a lot of curriculum learning stuff within RL that seems super relevant. Of particular relevance is the Alice/Bob framework from "Intrinsic motivation and automatic curricula via asymmetric self-play" seems very similar to the work at hand.  Something that is interesting in the Alice/Bob framework that could be transferred over here is the notion of the generator wanting to make a puzzle hard, but not too hard, i.e. make it just outside the solvers current capabilities. 

Overall my assessment is that this paper doesn't quite meet the standard for ICLR. My two major critiques are (1) the related work is seriously lacking making it difficult to situate this work in a broader context. The authors also seem to miss the entire curricular learning literature. (2) The empirical evaluations are lacking. In particular, more thorough analysis of how the generator is behaving, the type of curriculum it learns, and the resulting impact this has on a trainable solver all are missing. Furthermore, more focus on trainable solvers would improve this work. 

I'm not an expert in this area so it is possible I misjudged the significance of this work. I'm certainly open to revising my assessment if the authors are able to address (2) in a meaningful way. 


review_title: Official Blind Review #2

final_score: rating: 8: Accept
review_content: This paper proposes a method for generating hard puzzles with a trainable puzzle solver. This is an interesting and important problem which sits at the intersection of symbolic and deep learning based AI. The approach is largely GAN inspired, where the neural solver takes the role of a discriminator, and the generator is trained with REINFORCE instead of plain gradient descend.

Although I'm not an expert in this area, I have found this paper well written and easy to follow. The problem is well motivated, and the approach is sensible. As this is a novel problem, the paper also defines their own metric, namely the average time taken to solve the puzzle by given solvers, and the diversity of generated puzzles. It is nice to see that the generator indeed learns to generate puzzles that are significantly harder than random counterparts, while maintaining reasonable diversity. Although I think these are convincing results, my question to the authors is: have you tried or considered other ways of evaluating the generated puzzles? E.g., if you train the guided search solver on the generated puzzles and evaluate it on a random set of puzzles, would you see an improvement? I think this would be interesting to see, which can serve as an alternative evaluation metric.

My other comments are regarding the experiment section:
1. It would be useful to provide references to the solvers used, both in the adversarial training phase and the evaluation phase, if there is any.
2. More details of the training process would also be valuable. E.g., the training time and stability, common failure modes if any.

Minors:
1. Figure f3 should be s.count("A")==1000 and s.count("AA")==0 
2. First sentence under Fig 1, one is give -> one is given
3. Figure 5, f2: 2**(x**2)) == 16 -> 2**(x**2) == 16
review_title: Official Blind Review #3

Meta-review: The authors introducing programming puzzles as a way to help AI systems learn about reasoning. The authors then propose a GAN-like generation algorithm to generate diverse and difficult puzzles.

This is a very novel problem and the authors have made an interesting submission. However, at least 2 reviewers have raised severe concerns about the work. In particular, the relation to existing work as pointed by R2 was not very clear. Further, the paper was also lacking a strong empirical evaluation of the proposed ideas.  The authors did agree with most of the comments of the reviewers and made changes wherever possible. However, some changes have been pushed to future work or are not feasible right now. 

Based on the above observations, I recommended that the paper cannot be accepted now. The paper has a lot of potential and I would strongly encourage a revised submission addressing the questions/suggestions made by the reviewers.
Decision: Reject