Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: GALOIS introduces a DSL synthesis framework for reinforcement learning that combines both imperative and declarative programs. 
It takes in a sketch of proof, in the form of an inter-procedural control flow graph, then fills in the "holes" in the graph via synthesizing declarative programs. 
The contributions of this paper include:
1. A new domain-specific language for synthesizing a hierarchical program
2. A synthesize algorithm of this DSL
3. Evaluations comparing GALOIS and various baselines, showing GALOIS has better performance.
strengths_and_weaknesses: Originality: 3/5 

The paper designed a hybrid DSL for the reinforcement learning environment. Although template-based reinforcement learning and template generation are studied under a reinforcement learning setup, this work focuses on causal-effect by combining the imperative program and declarative program together, which is not studied before.

Quality: 3/5

Pros:
1. This paper shows a variety of baseline comparisons on the box task.
Cons:
1. The environment only has the "box-world" environment evaluation, but not another one.
     a) What are the user input and difficulties to adapt this approach to another setup?
     b) Performance comparison (minor)

Clarity: 2.5/5

Pros: The intuition and $DSL_{hybrid}$ are explained pretty clearly.
Cons:
1. The formalization is not clear enough. Specifically,
    a) How is the action space incorporate into the program synthesis is not clear in the formalization.
    b) How the rule head atoms are selected is not clear, such as "gt_key". What's more, how are they semantically aligned with the rule body?
    c) Can you explain more about the "normalized weighted vector $\theta_\rho^\psi$?
    d) It would help a lot to include a running example 

Significance: 3/5
This approach performs much better than both the pure neural approach and the current program synthesis approach. 
questions: 1. Can you explain more about the predicate deduction process, and the $normalized weighted vector $\theta_\rho^\psi$?
2. Can you explain the user interface on the framework. The user requires to provide the ICFG, but what about the head nodes?
3. In general, how is the action space incorporated into the program synthesis process?
4. It would be helpful to include another environment to demonstrate adaptability as a general framework. 
limitations: The authors addressed the limitations of this approach.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper presents GALOIS, a novel method to synthetize interpretable sketch-based programs. The authors propose a new DSL combining features of declarative and imperative languages. This DSL enables learning to synthetize logic hierarchical programs which generalize better than their fully-neural counterparts. The authors also conducted an extensive evaluation of GALOIS on several MiniGrid environments showing better generalization capabilities, performance and reusability over multiple tasks. 
strengths_and_weaknesses: The paper is interesting, since it enables us to generate highly-generalizable and explainable programs in an end-to-end fashion by providing also interpretable logical rules. As far as I know, the approach seems novel and I find it very impressive that we are able to synthesize a logical program directly instead of distilling it from a trained RL agent. 

I think the paper is moving in the right direction, however, certain parts of the paper and some details are not very clear. For example, I found Section 3.2 and Section 3.3 a bit hard to follow. I also feel that the paper does not describe some initial assumptions (e.g., DSL used, how the baselines are trained) needed to understand the impact of GALOIS over DNN counterparts. 

Program-sketches are heavily dependent on the problem we are trying to solve. Why is the proposed sketch more robust or why is it able to generalize better over multiple problems? I also mildly agree with the statement that “modifying or redesigning the sketch is also effortless.” (line 179-180). It does require quite a bit of effort and expert knowledge. If done wrong, it can hinder the overall final performance of the learned program. 

On line 212, the paper says that the model is trained based on “the experience collected by interacting with the model”. How do you collect these experiences? Do you run a partial sketch and do you keep only the successful trajectories? How is a policy defined? Since it is a program that interacts with the environment, the actions are also deterministic, so there is no real policy.

I do not fully agree with the claim stated at lines 245-249. Performance depends heavily on the DSL used. For example, if the DSL does not provide any branching statement (e.g., if-then-else) based on the environment features, then clearly it is impossible to synthesize a correct program. GALOIS might just have a better and more descriptive DSL than its counterpart.  The paper and Appendix lack a description of the DSL used by the neural competitors, thus it is hard to understand if GALOIS is actually better in the MultiRoom environment. 

Moreover, in the Appendix it is stated that the baselines use “2-layer multilayer perceptron (MLP) with 128 neurons in each layer” (lines 37-38). In my opinion, they hardly classify as deep neural networks. It would be interesting to see what happens if we increase the width/depth to more than 2 layers, thus having more realistic baselines. I would expect to see an increase in the convergence time, which would already justify why GALOIS is better, but also more realistic performance measurements. Additionally, regarding Section 4.3, worse performances on larger environments could also be caused by having shallow architectures on the baselines. 

Minor issues:

Line 43: programs … have limited generalizability

Line 94: a procedure defined based…

Line 339: prorgam-synthesis —> program-synthesis
questions: Summarizing some points expressed above:

- Which are the functions, namely the A set, available to both GALOIS and the baselines?
- How do you learn the sub-program needed by GALOIS (e.g., gt_key() or gt_door())? I assume these programs need to be learned somehow.
- Which is the DSL used by the neural baselines?
- Why is the proposed sketch design more robust or why is it able to generalize better over multiple problems? Basically, why did you choose to structure the sketch like that?
- How do you collect the train experiences for GALOIS? Do you run a partial sketch and do you keep only the successful trajectories? 
- How is a GALOIS policy defined (see equation line 215)?

limitations: One potential drawback of this method is the fact that we are constrained to filling a program sketch. Therefore, I could imagine finding tasks for which the given sketch cannot be used successfully. Moreover, feature engineering is still required to define a good set of atoms (e.g., is_key(X)). Without a good set of atom features, then not even GALOIS would be able to solve certain tasks.

Lastly, learning causal-effect relationship in an environment is a problem which overlaps naturally with the topic of causality [1] in machine learning. In the past years there have been some initial works on causality-inspired RL agents (e.g., [2]), which can learn more profound causal-effect relationships by interacting with the environment. Although these works are tangential to program synthesis, it would be interesting to investigate how to learn program-based policies informed by a causality notion. In theory, we could be able to generate highly-generalizable programs without the need for ILP formalization and/or FOL formalization.

[1] Pearl, Judea. Causality. Cambridge university press, 2009.

[2] Dasgupta, I., Wang, J., Chiappa, S., Mitrovic, J., Ortega, P., Raposo, D., ... & Kurth-Nelson, Z. (2019). Causal reasoning from meta-reinforcement learning. arXiv preprint arXiv:1901.08162.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes GALOIS, where the model learns a hierarchical logic program to represent the policy for solving a task. They first design a fixed program sketch represented as an inter-procedural control flow graph (ICFG), which includes 3 code blocks. The model needs to generate several definite clauses in each code block. The model is trained with policy gradient to maximize the expected cumulative return. They evaluate GALOIS on several tasks using the MiniGrid environment. Besides comparing to mainstream DRL methods, they also compare GALOIS to another program synthesis method that generates programs without conditional statements. Experimental results demonstrate that GALOIS generalizes better to test environments that share some similarities to the training environment.
strengths_and_weaknesses: Program synthesis for learning RL policies is an interesting and important problem. In particular, representing the policy as a hierarchical logic program has a lot of benefits, including generalizability, interpretability, and potentially solving more complicated tasks. The program sketch and DSL designed in the GALOIS framework are well-suited for experiments in this work, and the authors conduct an extensive comparison of different methods.

While GALOIS demonstrates superior performance over baseline methods, I think the performance gain largely comes from the domain-specific knowledge encoded in atoms and program structures. Below are related questions.

1. How large is the program search space for each task? From Figure 1 in the appendix, I feel that the atom set is specialized for each task, though sometimes the atom set is shared among similar tasks. Then for each definite clause in code blocks, actually the head atom and the atom list in the body can also be fixed, and the model simply needs to predict whether there is a negation for each atom. In this case, the comparison to MPPS is a bit unfair, given that MPPS does not leverage a program sketch that already contains conditionals and loops.

2. In Section 4.2, I think the generalization capability largely comes from the design of subgoals, as shown in Figure 7. Related to my first question, I wonder how these subgoals are predicted in the first code block, because some of them are unnecessary if only considering the training environment.

3. How would GALOIS work on other benchmarks, e.g., those evaluated in the MPPS paper?
questions: 1. How large is the program search space for each task? From Figure 1 in the appendix, I feel that the atom set is specialized for each task, though sometimes the atom set is shared among similar tasks. Then for each definite clause in code blocks, actually the head atom and the atom list in the body can also be fixed, and the model simply needs to predict whether there is a negation for each atom. In this case, the comparison to MPPS is a bit unfair, given that MPPS does not leverage a program sketch that already contains conditionals and loops.

2. In Section 4.2, I think the generalization capability largely comes from the design of subgoals, as shown in Figure 7. Related to my first question, I wonder how these subgoals are predicted in the first code block, because some of them are unnecessary if only considering the training environment.

3. How would GALOIS work on other benchmarks, e.g., those evaluated in the MPPS paper?
limitations: The authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

Meta-review: metareview: All reviewers liked the presented GALOIS framework to synthesize hierarchical and cause-effect logic programs that represent policy for solving a task. The use of program sketches to represent the search space and using policy gradients to learn the programs is also quite interesting. However, there were some concerns about the generality of the approach, the amount of human knowledge required in the provided sketch, limited evaluation environments, and scalability of the synthesis approach. The author response helped quite a bit towards many of these concerns. It would be great to incorporate the additional discussions and evaluations from the response in the next paper version.
confidence: Less certain
Decision: Accept