Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper approaches reinforcement learning from a program synthesis perspective and proposes a new method - LEAPS - that is capable of learning programmatic policies just from weak reward signals. This is achieved in two steps:
i) learning a smooth latent manifold where similar programs are encoded close to each other;
ii) searching the latent space efficiently via the Cross Entropy Method.
LEAPS is applied to several tasks in the Karel domain where it successfully can learn programmatic policies that are even transferable to larger state spaces for zero-shot learning.
main_review: I enjoyed reading the manuscript and found some of the presented ideas quite interesting. As noted by the authors, the problem of synthesizing programs directly from weak reward signals is quite challenging and so other works utilize entire traces for supervision or resort to program templates. In contrast, the proposed approach is capable of synthesizing programs from the ground up using a predefined DSL that contains loops, conditional statements and domain dependent actions and perceptions.

At the core of this novel capability is the set of behavioural losses used to train a varioational autoencoder resulting in a latent space where programs with similar behaviours are grouped closer to each other. While the proposed program behaviour loss is an obvious step towards building a program autoencoder, the latent behaviour loss is a non-trivial addition which according to the ablation studies makes a sizeable contribution to the performance of the model. How did you choose the architecture of the neural program executor module and were there any speasdcial considerations driven by the DSL and family of supported programs? Once trained how closely did the neural program executor can actually match the execution of the ground truth program?

Another question that I have regarding the behavioural losses is why did you decide to use just actions? Wouldn't action-state sequences provide a stronger supervision signal especially when only fragments of the execution of the reconstructed program semantically match the ground truth trace?

The analyses, experiments and reported results clearly demonstrate that LEAPS does provide RL agents with the capability to learn programatic policies that can even generalize to larger worlds. However, there are a few more results which may be reported that I think would increase the quality of the paper:

1) Traversals of the program latent space and visualizing interpolations between different programs. This will really shed more light on what the learnt latent space looks like.

2) More explicit information about the computational resources and time needed to run the various experiments.

3) At least one plot showing how the best found program evolves over the course of searching - complexity and losses.

Lastly, in figure 15 in the appendix the CEM search is described as converging to the ground truth solution, but the population of candidate solutions in fact passes right by the ground truth and never actually returns to it. Can you explain this phenomena?
limitations_and_societal_impact: I think the biggest limitation of the proposed paper is the fact that only relatively short programs are considered. This of course is a result of the simple grid world the Karel domain defines. Therefore, it will be very interesting to see LEAPS applied to tasks that require more complex and compositional behaviours. Additionally, as mentioned by the authors, bringing LEAPS to the robotics domain will be a great step towards synthesizing robust robotics policies, however, I believe for that the LEAPS framework will need to be extended to handle learning perception modules and action controllers simultaneously with the policy search.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper presents a two-stage method for reinforcement learning via program synthesis, and shows that is is effective compared to baselines for a number of simple gridworld tasks, deminstrating a degree of out-of-distribution generalisation. The first stage of the process learns a latent space for encoding programs, and the second stage searches that latent space for programs that maximise reward in  the task. Overall a very nice paper that deserves publication.
main_review: This is a very substantial and impressive piece of work. Program synthesis is a very promising avenue for building RL agents that achieve better generalisation, and whose representations are humanly interpretable. A major accomplishment of this paper is to learn embeddings of programs (in a variant of the Karel language) using a VAE with a recurrent encoder and decoder and three different losses. (I’m not sufficiently famiiar with recent ML literature on program synthesis to know whether this is wholly new - so I rely on other reviewers to confirm this - but it seems like a significant step to me.) The authors carry out an extensive evaluation, with careful ablations, and show the effectiveness of the approach on a number of (admittedly quite simple) RL tasks. The most important result, to my mind, comes towards the end of the main text, which is to show that learned programs generalise to out-of-distribution grid sizes, where other approaches fail. The paper is clearly written and logically organised, although the method is complex, which means that a lot of referring to the Appendix is needed to follow it. (This is not a criticism, of course; it’s just a corrolary of the page limit.) Extensive material is supplied in the Appendix to back up the main paper.

There are quite a few issues in the definition of the DSL in Figure 1.

1) “while(b)” should be “while(b): s”

2) the definition of “Perception” is, at present, unused. I suspect the authors meant to write “Percept h” rather than “Perception h”, and to write “percept h” in the definition of a “Condition”.

3) Since negation is the only logical operator, the definition of  “Condition” should perhaps be simply “percept | not percept”. (Or rather “percept h | not percept h”; see (2).) At present it allows for, say, “not not not not percept”, which probably unintended, and surely unnecessary.

4) Don’t you need some brackets in the grammar? Otherwise how do you distinguish “while(B): (S1 ; S2)” from “(while(B): S1) ; S2”? (Obviously this isn’t an issue in normal Karel, where white space is used to indicate structure.) Indeed, from the examples in the Appendix (Fig. 6), it’s clear there are more symbols used in the code than in the grammar of Fig. 1, such as “c(“ and “)c”, which fulfil this bracketing function, as described in the caption. It’s a minor thing, but I feel the DSL grammar in Fig. 1 should be made to match this; it’s really a syntactic variant of Karel.

Section 4.1: I was very curious, at this point, to know what the architecture of q_phi and p_theta was. It took me a while to hunt them down in the Appendix (Section F6). A pointer to this material in the main text (Section 4.1) would be helpful.

In the Appendix (Section F6), you state “we utilize a syntax checker … at the output of the decoder to limit predictions to syntactically valid tokens”. How do you do this? Does the training loop just skip to the next sample if a syntactically incorrect program is generated? This can’t be right? How do you use the syntax check?

How do you sample from the set of possible programs in order to learn the program embedding? Do they all carry out meaningful behaviours? Do they all terminate?


TYPOS

Lines 81-82: “This limit the set of synthesizable programs” -> “This limits the set of synthesizable programs”

Lines 108-109: “view this objective is a special case” -> “view this objective as a special case”

Figure 3 caption: “tasks that demands certain behaviors” -> “tasks that demand certain behaviors”

Line 166: “ through supervised instead of RL gradients” -> “ through supervised learning instead of RL gradients” (presumably)

limitations_and_societal_impact: The authors include some material in the Discussion
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper suggests representing policies for MDPs as programs, and shows how to learn programmatic policies effectively from a mix of trial-and-error experience on specific tasks and a pre-training phase to create an embedding that maps programs producing similar behaviors into similar points in the embedding. The authors compare their method to a variety of baselines, including both ablations of their own model as well as more traditional approaches from hierarchical RL, deep RL, and a standard program synthesizer on the KAREL domain. The authors find that the programmatic policy representations perform better overall for many of the KAREL tasks, and generalize better to larger problems than they were trained on.
main_review: The paper’s pros (thoroughly done scientific experiments, a different perspective on how to build generalizable policies for MDPs, and considered framing and discussion pointing out its own limitations) slightly outweigh its cons (missing related work from classical planning, confusion about the possibility for loops in decision trees, and statistically borderline results in some experiments), and I believe this paper presents a reasonable scientific effort that will be interesting for a subset of the NeurIPS community.

In the next sections I go into pros and cons in more detail, and point to areas that I would like the authors to comment on/address in their revisions. ++ is pro, -- is con.

Related work:
++ The authors do a reasonable job of situating the work with respect to other efforts to synthesize programmatic policies from deep RL agents, program synthesis approaches, and limitations of finite state machines

-- The authors make statements about decision trees not handling loops several times in the paper, but that is a somewhat misleading statement. It is possible to include loops in decision trees, but these loops must be encapsulated differently within the DSL (see Silver et al, AAAI 2020 for an example where they use a “scanning” function that operates like a while loop within a decision tree context). In the author’s DSL, I think this would amount to having a separate “Loop l := while(b, s)” and to make the program “p:= DEF run() : s | l”. There are certainly limitations to this, and these loops cannot be generally as expressive as doing full program synthesis, but I think this statement should be watered down (or removed) within the paper. It might help to reference Silver 2020 to point out the limitations of such setups of while loops in decision trees.

-- There is a missing body of work from classical planning on synthesizing policies as programs in these same structures, two references below
1. For synthesizing for loop and while loop policies: LoopDistill (Elly Winner and Manuela Veloso, 2007)
2. For learning policies as programs in a more expressive space: Learning Teleoreactive Logic Programs from Problem Solving (Choi and Langley)

Results:
++ I appreciated the thoroughness of ablations covering all main aspects of the program embedding learning, and the method was (mostly) explained clearly.
++ There were many comparisons to baselines, and these baselines were mostly appropriately chosen for the domain to underscore the points of the paper (HRL to address extended actions vs. extended actions as programs, DRL-abs to address differences in input representation, VIPER to address at least one alternative program synthesis approach (although there are others that are “neural” and might have been more appropriate, such as REPL, Ellis et al 2019)). The baselines’ hyperparameters were also reasonably optimized, as outlined in the supplement.

++ The authors included exceptionally extensive supplementary material (31 pages!) with some nice visualizations of the learned program embeddings, extra details needed to reproduce the main experiments, extra experiments on transfer to unseen configurations of KAREL tasks, and code.

-- many of the results are statistically insignificant given the enormous standard deviations in the tables, especially in the program reconstruction. While it seems like the full LEAPS model performs statistically better than the naive model, it *does not* seem to perform better than the baselines in a statistically significant way.

-- it would have been nice to get some insight for why DRL-abs does not always perform better than DRL, as well as how these models were trained/how their parameters were validated. Could the authors comment on this?

-- why can VIPER not solve the generalization task? If it’s also operating on the abstract space, I would have thought it should be invariant to the grid size since it will only have information about objects in the environment? Similarly why did the authors only evaluate generalization on StairClimber and Maze? It should be trivial to expand all of the problems to larger grids and it seems a bit weird to pick only 2.

-- a simple way to keep the observation size the same for DRL between different problem sizes, which would also be a more fair comparison to the LEAPS model, would be to use a fully connected network (Long*, Shelhamer*, Darrell, 2015) as the policy, as that will look at grid locations in a more local way and be invariant to problem size (see Silver, 2020 who similarly found that this type of network significantly out-performed a fully connected model for changing grid sizes). This might perform much better than the current method while also generalizing better, and be a good test of whether it’s the programmatic structure of the policy that is required, or if it’s more of a “locality” or “relational” requirement.

-- I think details about the RL aspect of the test tasks needs to be made very clear. E.g. how many episodes does an agent get within each task? How many training tasks do the DRL agents receive before they are evaluated? How are the training tasks for these distinguished from the test tasks for generating the numbers in Table 3?

Discussion
++ excellent pointers to limitations of the work - a crucial component of ML papers.
-- I would have liked to see a little more discussion on why programs specifically vs. hierarchical policies vs. abstract action spaces, and how this kind of approach would be expected to work for problems that are not specifically designed for program synthesis techniques. However I recognize there isn’t too much space and the authors alluded to this in the results sections.

limitations_and_societal_impact: Yes they have addressed these adequately.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: - Authors use a two-stage method for program synthesis: (1) They
  create an embedding space capturing the semantics of the program
  space; (2) They search through the embedding space for a program
  that solves the task in hand.
- They use variational autoencoder to encode programs, where an
  encoder maps a sequence of program tokens into a latent space, while
  a decoder maps from the latent space into the original program. They
  use a combination of loss functions to ensure that not only
  syntactically similar programs are close to each other in the latent
  space but also semantically close programs. Loss function consists
  of a composition of 3 losses. (A) Classical beta VAE loss which
  helps that syntactically close programs are close to each other. (B)
  Program behavior reconstruction loss which helps that semantically
  similar programs are close to each other in the embedding space. For
  example, two syntactically different programs can make same actions
  under same situations. This loss is defined by difference between
  execution traces of original and reconstructed program. (C) Latent
  behavior reconstruction loss. This loss is constructed by learning a
  policy to predict correct action based on the latent program
  embedding. This allows for backpropagating gradient through the
  policy and the encoder to ensure better quality of the embeddings.
- After training the variational autoencoder, authors use a cross
  entropy method to find a program with maximal performance using the
  latent space. They sample the latent space distribution of programs,
  decode the latent program into an actual program, execute the
  program to obtain corresponding rewards, and repeat the process.
- Authors did a nice ablation study where they measured effectiveness
  of their individual design decisions: evaluating each of the loss
  function components, as well as the effectiveness of the latent
  space search method for finding the best performing program. They
  compared they method to other methods, deep reinforcement learning
  (DRL) based as well as Viper which is a decision tree policy
  obtained by mimicking a DRL agent.
main_review: - Originality: I find the approach to be novel, creatively designing
  loss functions ensuring quality latent space representation of
  programs.

- Significance: Program synthesis is an important and challenging
  research area, and thus I find the problem being solved
  important. Technique is illustrated on a simple (Karel) tasks which
  might seem insufficient, but the program synthesis field is still at
  the stage where small problems are hard to solve, thus I find the
  choice appropriate.
  
- Paper is well written and easy to follow. In addition, authors
  provide extensive appendix and accompanying web page with useful
  information.

- Figure 2 is very informative. I would suggest extending the caption
  of the figure so it is more self-contained. For example, explain
  what policy Pi is, as well as a1, a2, etc. I understood different
  parts of the figure only when I thoroughly read the paper.

- In the future, it would be good to evaluate the approach on tasks
  that are outside of the Karel domain.

- I do not have a good track of other approaches that can be used for
  synthesizing Karel programs, and thus am not certain if all relevant
  approaches are included in the comparison.

- Questions
    - Have you considered different ways of generating programs than
      pure random generation? Are there many programs that are 'not
      interesting' when performing random generation?
    - Program Embedding Space Smoothness. Is there a specific reason
      why embedding space search is performed on the train/val set, vs
      test set? Does the same trend apply to the test set?
    - In Table 2, do results represent percent of times that execution
      traces of two programs match (averaged across program pairs)? I
      understand that Rmat is defined as number of times traces match,
      not percent of times.
    - equation 4 (latent behavior reconstruction loss): Loss is
      referred to as a cross entropy loss. However, EXECt(ro) seems
      incorrect as it's constant in the inner sum. I assume it should
      be 1 in a case of the executed action, and 0 otherwise?

- Minor
    - Line 233: "shown in Figure 6". This figure is not in the main
      text.
limitations_and_societal_impact: Authors did cover these areas. They could elaborate how does their approach scale to other domains.
review_title: null

Meta-review: This paper presents an interesting idea of learning policies for solving RL problems through program synthesis.  The key is to learn a good program embedding space, through 3 different losses that take care of 3 different aspects of a program representation.

The reviewers all appreciate the clarity of the paper and liked the idea.  The extensive ablations and supplementary material are also great for supporting the proposed approach.

In the future showing that this approach works on other domains beyond Karel, e.g. Minecraft and CARLA as suggested by the authors in the discussion, would be great.
Decision: Accept (Poster)