GALOIS: Boosting Deep Reinforcement Learning via Generalizable Logic Synthesis
Authors: Yushi Cao
Zhiming Li
Tianpei Yang
Hao Zhang
YAN ZHENG
Yi Li
Jianye HAO
Yang Liu
Venue: NeurIPS 2022 Accept (2022)
Keywords: deep reinforcement learning
program synthesis

Abstract: Despite achieving superior performance in human-level control problems, unlike humans, deep reinforcement learning (DRL) lacks high-order intelligence (e.g., logic deduction and reuse), thus it behaves ineffectively than humans regarding learning and generalization in complex problems. Previous works attempt to directly synthesize a white-box logic program as the DRL policy, manifesting logic-driven behaviors. However, most synthesis methods are built on imperative or declarative programming, and each has a distinct limitation, respectively. The former ignores the cause-effect logic during synthesis, resulting in low generalizability across tasks. The latter is strictly proof-based, thus failing to synthesize programs with complex hierarchical logic. In this paper, we combine the above two paradigms together and propose a novel Generalizable Logic Synthesis (GALOIS) framework to synthesize hierarchical and strict cause-effect logic programs. GALOIS leverages the program sketch and defines a new sketch-based hybrid program language for guiding the synthesis. Based on that, GALOIS proposes a sketch-based program synthesis method to automatically generate white-box programs with generalizable and interpretable cause-effect logic. Extensive evaluations on various decision-making tasks with complex logic demonstrate the superiority of GALOIS over mainstream baselines regarding the asymptotic performance, generalizability, and great knowledge reusability across different environments.

GALOIS: Boosting Deep Reinforcement Learning via Generalizable Logic Synthesis
Yushi Cao?: Zhiming Li Tianpei Yangl. 13.,, Hao Zhang',
Yan Zheng l.
Yi Jianye Hao', Yang Liu College of Intelligence and Computing, Tianjin university, Tianjin, China 2 Nanyang Technological University, Singapore, University of Alberta, Canada fyushi002, zhiming001)0e ntu. edu. (tpyang.3118216216 301821621,, yanzheng, jianye. hao)etjj.. edu. en {yi_ yangi,yangguu ennuu @ntu. edu.sg
Abstract
Despite achieving superior performance in human-level control problems, unlike humans, deep reinforcement learning (DRL) lacks high-order intelligence (e.g.. logic deduction and reuse), thus it behaves ineffectively than humans regarding learning and generalization in complex problems. Previous works attempt to directly synthesize white-box logic program as the DRL policy, manifesting logic-driven behaviors. However, most synthesis methods are built on imperative declarative programming. and each has distinct limitation, respectively. The former ignores the cause-effeci logic during synthesis, resulting in low generaliz- ability across tasks. The latter is strictly proof- proof-based, thus failing to synthesize programs with complex hierarchical logic. In this paper. we combine the above two paradigms together and propose novel Generalizable Logic Synthesis (GALOIS) framework to synthesize hierarchical and strict cause-effect logic programs. GA- LOIS leverages the program sketch and defines a new sketch-based hybrid program language for guiding the synthesis. Based on that, GALOIS proposes a sketch- based program synthesis method to automatically generate white-box programs with generalizable and interpretable cause-effect logic. Extensive evaluations on various decision-making tasks with complex logic demonstrate the superiority of GALOIS over mainstream baselines regarding the asymptotic performance, generalizability, and great knowledge reusability across different environments.
Introduction
Deep reinforcement learning (DRL) has achieved great breakthroughs in various domains like robotics control 277, video game (24), software testing [48] [1 5), etc. Despite its sheer success, DRL models still perform less effective learning and generalization abilities than humans in solving long sequential decision-makin problems, especially those requiring complex logic to solve [16] 40). For example, a seemingly simple task for robot arm to put an object into a drawer is hard to solve due to the complex intrinsic logic (e.g., open the drawer, pick the object, place the object, close the drawer) B3) Additionally, DRL policies are also hard to interpret since the result- souult-enerating processes of the neural network remain opaque to humans due its black-box nature 35 28
To mitigate the above challenges, researchers seek the programming language, making the best of both connectionism 330 and symbolism 43 to generate white-box programs as the policy to
"quual contribution.
Corresponding authors: Yan Zheng (yanzheng cattrheenn@@uu.dd.com and Tianpei Yang (tpyang @ tju.edu.cn)
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

execute logic-driven and explainable behaviors for tosk-solving. Logic contains explainable task- solving knowledge that naturally can generalize across similar tasks. Therefore. attempts have been made to introduce human-defined prior logic into the DRL models 46]. Human- logic programs are found to be an effective way to improve the learning performance and zero- shot generalization [40]. However, such a manner requires manually written logic programs be- forehand for each new environment, motivating an urgent need for automatic program synthesis. Existing program synthesis approaches can be categorized into two major paradigms: imperative and declarative programming 6 36 29], gramming aims to synthesize multiple sub-programs, each has different ability to solve the problem, and combine them se- quentially as a whole program [44] 15 [7]. However, programs synthesized in such way has limited generalizability and inter- pretability since the imperative programming only specify the post-condition (effect) while ignores the pre-condition (cause) of each sub-program, which is regarded as a flawed reflection of cau- sation [8] that is prone aliasing. In other words, the agent will arbitrarily follow the synthesized program sequentially without knowing why (i.e., cause-effect logic). For example. assume a task in Figure [ that requires the agent to open the box, get the key, open the door, then reach the goal. The synthesized imperative pro- gram would contain uub-programs: toggle_ box (); get key O) open_ oven_door(( (); reach_ O) each should executed sequentially (the blue path). However, when applying such a program to another similar task with minor logical differences: the key is placed outside the box, meaning the agent does not need to open the box. The synthesized program becomes sub-optimal as the agent will always follow the program to open the box first. However, the optimal policy should directly head for the key and ignores the box (denoted as the orange path).
each has its distinct limitation. The imperative pro-
Programs:
boxl::
get Jayy:
open dcont:
Figure 1: A motivating example.
On the other side, declarative programming aims to synthesize programs with explicit cause-effect logic [16 10) in the form of first-order logic (FOL) (26). requiring the programs be built on the proof system (i.e., verify the trigger condition given the facts, then decide which rule should be activated) 4 However, due to the trait of FOL, programs synthesized in this way lack hicrarchical logic and thus are ineffective in solving complex tasks [I]
To combine the advantages of both paradigms and synthesize program with hierarchical cause-effect logic, we propose a novel Generalizable Logic Synthesis (GALOIS) framework for further boosting the learning ability, generalizability and interpretability of DRL. First, GALOIS introduces the concept of the program sketch (38] and defines a new hybrid sketch-based
cornain-speciffe language (DSL), including the syntax and semantic specifications, allowing synthesizing programs with hicrarchical logic and strict enfse-effect logic at the same time. Beyond that, GALOIS proposes sketch- based program synthesis method extended from the differentiable inductive logic programming (12), constructing general way to synthesize hierarchical logic program given the program grogram-sketch. In this way, GALOIS can not only generate hierarchical programs with multiple sub-program synergistic cooperation for task-solving but also can achieve strict cause-effect logic with high interpretability and generalizability across tasks. Furthermore, the synthesized white-box program can be easily extended with expert knowledge tuned by humans to efficiently adapt to different downstream tasks. Our contributions are threefold: (1) a new skatch-based hybrid program language is proposed for allowing hierarchical logic programs for the first time, (2) general and automatic way is proposed to synthesize programs with generalizable cause-effect logic, (3) extensive evaluations on various complex tasks demonstrate the superiority of GALOIS over mainstream DRL and program synthesis baselines regarding the lcarning ability, generalizability, interpretability, and knowledge (logic) reusability across tasks.
The implementation is available at: httpps//sites. seciitess.oogg google. wwwp:/oo.ooowoooooooooooooccccee wttp://wwwwwwwo.oo...oo..

---

2 Preliminary
2.1 Markov Decision Process
The sequential decision-makinn problem is commonly modeled Markov decision process (MDP), which is formulated as a 5-tuple (S, A, R. P) where is the state space, A is the action space, R S A + R is the reward function, P S A S is the transition function, and À is the discount factor. The agent interacts with the environment following a policy т ((ar(s)) to collect experiences {(1t, de, rt)) where T is the terminal time step. The goal is learn the optimal policy n² that maximizes the expected discounted return: π. arg max, Eawr 12 Xr..].
2.2 Inductive Logic Programming
Logic programming is programming paradigm that requires programs be written in a definite clause, which is of the form: H :- Ai..., An, where H is the head atom and .i.....44 An, 2 0 is called the body that denotes the conjunction of n atoms, :- denotes logical entailment: H is true if A1 A A2... A A, is true. An atom is function (w ((......,,,, where v is a n-ary predicate and wi, E [1, n] are terms. predicate defined based on ground atoms without deductions is called an extensional predicate. Otherwise, it is called an intensional predicate. An atom whose terms are all instantiated by constants is called a ground atom. The ground atoms whose propositions are known in prior without entailment are called facts. Note that set composed of all the concerning ground atoms is called a Herbrand base.
Inductive Logic Programming (ILP) 19 is a logic program synthesis model which synthesizes logic program that satisfies the pre-defined specification. In the supervised learning setting, the specification is to synthesize logic program C such that YÇ, F. C } Ç, F, C o X, where Ç, A denotes positive and negative samples, the set of background facts given in prior; and for the reinforcement learning setting, the specification is to synthesize C' such that C = argmax, R, where R is the average return of each episode. Specifically. ILP conducted based on the valuation vector e {0, 1] I|l G denotes the Herbrand base of the ground atoms. Each scalar of represents the true value of the corresponding ground atom. During each deduction step, e is recursively updated with the forward chaining mechanism, such that the auxiliary atoms and target atoms would be grounded.
3 Methodology
3.1 Motivation
As aforementioned, solving real decision-making problems, e.g., robot navigation and control
4F1
451, commonly requires complicated logic. As humans, we use the sevidd-anddconquee concept to dismantle problems into sub- problems and solve them separately. It is natural to think of generating a hierarchical logic program to solve complex problems. This intuition, however, has hardly been adopted in program synthesis since the strict cause-effect effect logic program is intrinsically non-trivial to generate, let alone the one with hierarchical logic 36
In this work, we propose generalized logic synthesis (GALOIS) framework for synthesizing white-box hierarchical logic program (as the policy) to execute logically interpretable behaviors in complex problems. Figure 2 shows the overview of GALOIS, comprised of two key components: a sketch-based DSL, and GALOIS uses white-box program as the policy interact with the environment and collect data for policy optimization. Here, a new DSL is defined for creating hierarchical logic programs; and the sketch-based program synthesis method based differentiable ILP is adopted for generating effective logic for the policy synthesis. In this way, GALOIS can synthesize white-box programs with generalizable logic more efficiently and automatically.
sketch-based program synthesis method. is noteworthy that
3.2 Sketch-based Program Language
To synthesize logic programs with both hierarchical logic and explicit cause-effect logic, we design novel sketch-based DSL., namely Laybrid, absorbing both the advantages of imperative and declar- ative programming. Figure 3 shows the detail syntax and semantic specifications of Lhybrid. It is
3

---

Interaction
Program Skatch
Synthesize Logic Program
HBC
State
Action
Friry
Frnv
sytterti speditiation
codi block
Naomi SanniSSSann Sample
white-box
Verifying
program (Policy)
0g
code block N
0
Exit
Hastran
semurtic specitictionn
Skotching- based domnin spocific language
skettcit bosed ILP
Figure 2: Overview of GALOIS, where the (a) sketch -keech-based DSL defines what program can be syn- thesized, and (b) sketch- based ILP synthesizes programs with logic where fr. represents predicate of hole function p inference step and 0 is the corresponding weight.
Dedforaive Imrpsttivee
== c x x: z:=elc;o
WHERE C[??wHERE] . = (s(@ + C[AWHERE } gl
while do
HOW C]? (s, a) (s[ pos + C[Anow (@) F =d]s], []s),{)
f == R J ??
R == 4 A-list
WHAT C[? (s, (s(o C[AWHAT(S) = =ass)
A-list == AIAA A-list
(a) syntax
(b) semantics
Figure 3: The (a) syntactic and (b) semantic specifications of DSL hyybrid-
noteworthy that Lhybrid ensures the synthesized program follow strict cause-effect logic. Beyond that, following Chybrid, we synthesize programs using program sketches, allowing generating hierarchical logic programs. In the following, we describe the formal syntactic and semantic specifications first and illustrate how the program sketch derives hierarchical logic programs.
Syntactic Specification: The formal syntactic specifications of Lhybrid defined using elements from both the declarative and imperative language (shown in Figure (()). Intuitively, the declarative language demands the synthesized program follow strict cause-effect logic. while the imperative language enables programs with hierarchical logic. In specific, imperative language elements are be instantiated constant function call f. and
expression and command Term be assignment statement x == e, sequential execution c; c or control flow (while loop). Declarative language elements are function f and clause R. To expose cause-effect relations, constrains functions to be implemented declaratively: f : R R, where R represents logic clause in the form of :: - A-list, where A denotes atom and A-list is the clause body.
is noteworthy that, to implement the program sketch, we introduce novel language element called hole function, denoted ??. This hole function denotes unimplemented logic sub- aub-program (i.c., code block Figure 2 to be synthesized given the constraints specified by the program sketch and its corresponding semantic specification.
Semantic Specification: Having the syntactic spec- ification, any syntactically valid program sketch can be derived. However, without semantic guidance (e.g., lack of task-related semanties), the synthesized program may lack sufficient hierarchical logic to effi- ciently solve tasks [52]. Hence, we propose leverag- ing the program sketch 38 and defining associated semantic specifications to guide the synthesis to gen- erate hierarchical logic programs. In the following, we illustrate the details of the program sketch used in this work and its formal semantic specifications,
? ZyaEER
Entry
apranthy
? Phow
7 Pinow (9
careecct Flantat""
left(:: cumeni
M (3)
puk(): (r or Jeyy wha boy or (eggie() ku har key (.ceppet
Exit
Figure 4: (left) program sketch represented as ICFG and (right) the synthesized logic.

---

based on which sketching- kketching-based based inductive logic programming is performed. Specifically, as shown in the inter- therr-roceeural control flow graph (ICFG) illustration Figure 4 the program sketch contains three major basic blocks of hole functions (denoted as p) to be synthesized: ??WHERE, H?o and ?? WWWIA
During each round of recursion, the program first executes and checks whether termination condition satisfied, if not, an assignment statement is executed: 1 (:EREWH by calling a hole function: WHHEE We define the meaning of hole function following the formalism of standard denotational semanties 32 in F Concretely, for ?? WHERE the body of the synthesized clause AWHERE(S) is constructed from the Herbrand base representation of the current state s, namely objects' states and agent's attributes: GWHERE = (obj.)
E [1, ml. j [1, n1] (attr))) : x E [1. u], y e [1. o]}. The clause body entails the head atom 9, which denotes an abstract object within the environment (i.e., sub-goal that agent shall arrive during this round of recursion, e.g. key, box, etc.). The semantic function C[.] evaluates the clause and returns the relative coordinates between the agent and the subgoal. The return value passed to the logic sub-prog uub-program now (shown as the red dashed arrow). ?ow deduces the direction d of next time step the agent shall move to: pos + C[A (@) }= djs, where pos is the agent's next-time-step position after execution, Aнoо( @)) is constructed from Herbrand base which consists of ground atoms that applies predicates regarding numerical feature on the relative coordinates: GhOw = {e),(z) (z), ei (y) : = [1, ?ow executes recursively until the sub-god goal specified by WHEE is achieved. Finally, ??T deduces the action a to take to interact with the object at the sub-goal position: o + C[[AHHAT(S } als, where denotes the updated state of the interacted object. Note that the program sketch used is generalizable and can be applied to environments with different logic (see details in Section 4 For tasks whose environments significantly different from the ones evaluated in this work, modifying or redesigning the sketch is also straightforward [38 52)
3.3 Sketch-based Program Synthesis
GALOIS interacts with the environment to collect experiences to synthesize white-box programs with hicrarchical and cause-effect logic following Laybrid. As shown in Figure in the following, we illustrate how the program interacts with the environment, what is the structure of the program and how it is trained.
Practically, different from the black-box model, GALOIS requires different types of input and output. Therefore, GALOIS maintains an encoder E(-) and decoder D(-) to interact with the environment. F(s) maps the state 8 to a set of ground atoms (formatted as valuation vector ep) with the verification from Lhybrid, i.e., e, = Chybria)) )). As shown in Figure ( the leftmost squares with different color represents the atoms from different hole functions (e.g., blue squares [[WHERF] 1 denotes the atoms for WHEE (d denotes 1 howward-chiningg steps performed)). Based on Cp. GALOIS outputs predicate probabilities and the Decoder maps them to the action probabilities (i.e., a ~ D(p(e,)), where p()) denotes the deduction process).
In this way, the program is executable via fuzzy conjunction [1], and the program synthesis can be performed. Guided by the semanties of the hole functions, GALOIS performs deduction using the weights 0 assigned to each candidate clauses of the specific atom (i.e., one weight 0 in the weights vector 0 indicates one candidate clause). This process is shown in Figure b). The rightmost squares represent the final atom deduced in the corresponding hole function. GALOIS combines all the ground atoms to perform complex program. For example, fWHERE is inferred with conjunction between fWHEee and f122 JWHERE A learnable weight assigned to each candidate clause (e.g., WHERE associates with the clause: gt_key () :- ~has_kep (X), , is as_agent (X), has has_key(Y) is_env (Y) which derived with two steps of deduction, shown in Figure
Now we explain in detail how a certain predicate is deduced, Given initialized valuation vector set ep, the deductions of the predicates are:
p 0) -
softmax (0, (07*) @ (1))), & E (()
1
where ez denotes the valuation vector for all the atoms in hole function p at deduction step (initial- ized to 1), which is essentially a vector that stores the inferred truth values for all the corresponding atoms. @ denotes the probabilistic sum: x $ y x x x-yx- y. Specifically, given the normalized
5

---

(a) Dourkey
(b) BoxKey
(c) Unlockpickup
(b) Mullizuom
Figure 5: Visualization of various tasks in MiniGrid, each requires different logic to accomplish: (a) the (red triangle) agent aims to pick up the (yellow) key open the door (yellow box) and move to the goal (in green); (b) the agent needs to open the (gray) box to get the key first, then open the door to reach the goal; (c) the agent has pick up the key to open the door, and then drop the key to pick up the (green) box; (d) the agent need to open multiple (yellow, blue, and red) doors to reach the goal.
weight vector p for the predicate & in hole function p at deduction step т, to perform a single-step deduction, we take the Hadamard product @ of 07 and the one-step inference results based on the valuation vector of last forward-chaining step, where h(-)) denotes the inference function H We then obtain the deductive result by taking the sum of all the intentional predicates. Finally, the valuation vector is updated to be e, by taking the probabilistic sum of the deductive result and the last step valuation vector. Intuitively, this process is similar to the forward propagation of a neural network, while GALOIS uses logic deduction to generate results.
The policy is trained an on-policy manner. For each episode, the RL agent collects experiences {1t, (e; rx)) ) by interacting with the environment using current policy With the collected experiences, GALOIS can thus synthesize the optimal hierarchical logie program to get the maxi-
expected cumulative return: πg- arg maxy Ba-ws Σ (rr(se ae) where 0 denotes the
learnable parameters in GALOIS. We train it with the Monte-Carlo policy gradient
42
= + a Vo log ToQ a4) + VVH
where (TT) the entropy regularization to improve exploration [22] the 7. is the hyperparameter to control the decrease rate of the entropy with time.
4 Experiments
To evaluate the effectiveness of GALOIS, we study the following research questions (RQs):
RQ1 (Performance): How effective GALOIS regarding the performance and learning speed?
RQ2 (Generalizability): How is the generalizability of GALOIS across environments?
RQ3 (Reusability): Does GALOIS show great knowledge reusability across different environments?
4.1 Setup
Environments: We adopt the MiniGrid environments 7 which contains various tasks that require different abilities (i.e., navigation and multistep logical reasoning) to accomplish. consider four representative tasks with incremental levels of logical difficulties as shown in Figure
Baselines: Various baseline are used for comparisons, including mainstream DRL approaches, i.c., value-based (DQN (23)), policy-based (PPO [3]), actor-critic (SAC (33). hierarchical (h-DQN (20)) algorithms, and the program synthesis guided methods (MPPS 44).. To avoid unfair comparison, we the same training settings for all methods (see Appendix B for more details).
4.2 Performance Analysis (RQ1).
To answer RQL, we evaluate the performance GALOIS and other baseline methods in the training environment. The results in Figure Z show that GALOIS outperforms all other mainstream baselines in terms of performance in environments that require complex logic, showing that GALOIS can learn
Pleass refer to the F' function in the original paper 12 for specific details.

---

DoorKey
Boxkey
UnlockPickup
MultiRoom
1.0
1.0
1.0
Performance
0.8
0.8
15.
11.0
0.6
0.6
0.4
0..
0.5
0.4
0.2
0.2
MP5
000 1000
20000 1900 #Episode
4000
5000
0.0
1000
7005
1000
4050
5000
0.0
1000
2000
2000
4000
5000
0
1000
2000 300e #Episode
4000
5000
#Fpisode
#Episode
Figure 6: Comparisons of GALOIS and related baselines regarding the asymptotic performance and learning speed (all the results are averaged over 5 random seeds).
Table I: Average return on the training environment and corresponding test environments with different sizes, (v) denotes agent trained with valuation vectors, (tr) denotes the training environment.
MIONNN
0.975- 13
0919-mom
6:05-40
11919-0017
0.95-0 DOG
11926-01144
0.66--006
0.94440.00 001
1010
8.18800116
0 000440002
Donkee
12112
0000
050000175
0.537a1
0.53900 184
0.00
0100
0.15260 263
000
0,55 D4)
0:963
10914
012520022
000 109
0.36281144
0.725
0000000
100
10354822251
0 0504210227
(402
0955 101000
16115
000050000
087721110
016111101
0.20000005
0.750
000000000000
000
0055882235
694421
0065
18715
0:0000000
0.18440001
8734401775
000040
000
0911-0000
20P30
010000000
02100005
000000
100
1022442255
0061110077
0996 40
3'5:00)
034120.166
0300
0000
0.74
046889
279
0551250055
0 034
004721.00
0915
10110
017220012
0.02210911
CASOUN 160
0.2090015
0:39940
205
C111
Bockry
10114
12912
01022001222
0:00000000
0.5750005
0:335-0.151
041100114
0X3000014
030000074
034410064
0516:0003
033160 130
2222240222
0381
0 0500000000
0:917
C015
16916
0007-00012
0390-0015
0:305-0.00
025--001
0575-0007
0.13440 IM
0361-0
0001-41001
18118
0.000000000
022
0.13
0.56
0 0155550554
0545
009930 105
0.5665014
0 02 120
606221002
0:900
20133
010000000
0112520015
0109300011
615.om
0 032600310
0 0.4254111
TM
082-000M
DU00440 59
631341109
Cool (2)
818
0.34 0.00250:17
150
0.164911109
145
0.57ke0054
02
0.13780
235
0.77700:14
68722 105
0:33
Untecthhckp
10P10
12412
01902200000
03
0200
0042211012
0488a0.25
L19520045
G05180 102
0007700
164
082285271
0 02022000
6035a1102
CUS3
0051
10914
01000000000
0.77-00333
6017-40.009
0411440315 113
176-00019
0915-0014
083440001
0358-6005
10916
0100000000
00012401066
4
18118
0.000:00000
0.20500:66
6003
0.470e0.317
0.00200022
059050000
0000000000
0837660273
0.50060262
0.66500000
0100000000
0014-0008
0000
0100L0003
0.26.1006
0000400
RC00000000
NIA
10P10
01000000
(135501141
0140110000
0003040
Mullive
12412
10914
0:00-000000
0:00:000000
0:00000000
000000000
6000
6003-0
0.00000000 000
0:0000.003
0:00000000
0000000000
0:15500000
0107400000
0100000000
0.000000000
NOA
16116
0.000000000
0:00062:000
0.0021003)
0.10020
0000000
0.00020000
the comprehensive task-solving logic, leading to the highest performance. Note that in the DoorKey environment, all baseline methods can reach optimal training performance, and DQN converges the fastest. This is because the DoorKey environment is relatively simpler, whose intrinsic logic is easy to learn, and hierarchical models have more parameters than the DQN model, leading slower convergence speed. Moreover, we observe that MPPS, hDQN, and GALOIS converge faster than the methods without hierarchy in environments that require more complex logic (e.g.. UnlockPickup, BoxKey). We can thus conclude that introducing hierarchy contributes to more efficient learning. Besides, unlike other pure neural network baselines, GALOIS and MPPS present steadier asymptotic performance during training with also smaller variance. This result demonstrates the effectiveness of introducing program synthesis for steady policy learning.
Specifically, MPPS theoretically fails on MultiRoom as there exists no deterministic imperative program description (denoted N/A in T) The reason is that the sequence of colored doors that the agent should cross differs for each episode (e.g., epl: red_door--ee syellow_doox su__ddoo-rblus botor-blue_ddddd lowlllowddooo ow_door), thus the program on solving this task is dynamically changing, which fails the imperative program synthesizer. This further indicates the importance of synthesizing declarative programs with cause-effect logic instead of merely finding the ordered sequence of subprograms for solving tasks. More details are discussed in the following sections.
ep2:
4.3 Generalizability Analysis (RQ2).
To answer RQ2, we evaluate models' performance on test environments with different sizes and task- solving logic (i.e., semantic modifications). Concretely, as shown in Table I GALOIS outperforms all the other baseline methods (highest average returns are highlighted in gray) and maintains near-optimal performance. Furthermore, we also observe that all other baseline methods maintain acceptable generalizability. This contradicts the conclusion in [16] that neural network-based agents fail to generalize to environments with size changes. We hypothesize that this attributes to the use
7

---

Synthesized program
while goal
(1000 Jey agagemnN) hos kestY) a_en
1:2 (1.00) door)
doort))
seent,, over doent))
while subgool do
(0.55) aM0 V cucmee 0% (eg
letty VY cumeet post))
opo V Kommnnt
(0.89) XxneentX. poat)) Mhere
pick))
(1.00) -00. doon keylY
Buxkey
wed)
Figure 7: (left) shows the original and semantic- semantic-modifeed environments of UnlockPickup and BoxKey. The optimal traces are marked in orange; (right) shows the synthesized program for BoxKey.
Table Average return on test environments with semantic modifications.
DQN
SAC
PPO
hDQN
MPPS
Ours
BoxKey
8*B(L))
0.241a0.166
0.60840.046
0.71420.042
0.541
0.94980.003
0.975 10.001
semn-mud
0,04040.040
0.098+0.005
0. 16.+0000088
0,476*0.091
0.119:0.020
0.976 +0.001
12*6(tr)
0.23640.220
0.222
0.82620.054
0.82420.235
0.81320.039
0.901 10.021
UnlockPickuup
sem-mod
0.007+0.012
0.04000.005
0.09820.004
0.43420.390
0.000=0.000
0.983 +0.003
of different types of representations. To evaluate the effectiveness of using the valuation vector representation, we conduct experiments using the observations directly obtained from environments (e.g., the status and locations of objects). Surprisingly. though achieving decent performance in the training environment, all the vanilla neural network-based baselines perform poorly on test environments of different sizes. Therefore, we conclude that by introducing logic expression state representation (in the form of valuation vectors), better generalizability can be obtained. However, as illustrated by the results, the valuation vector itself not enough to achieve supreme generalizability, GALOIS manages to achieve even better generalizability due to explicit use of cause-effect logic with hierarchical structure.
We then evaluate models' generalizability on two test environments with minor semantic modi- fications, namely BoxKey (sem-mod) and UnlockPickup (sem-mod), as shown in Figure (eftt. Specifically, for UnlockPickup (sem-mod), different from the training environment, there is no key in the environment, and the door is already open. And thus the agent should head for the target location directly. For BoxKey (sem-mod), the key is placed outside the box. Thus, optimally, the agent should directly head for the key and ignore the existence of the box. The results in Table 2 the baselines are severely compromised while GALOIS retains near-optimal generalizability. This attributes its explicit use of cause-effect logic.
lindicate that all
Figure 7 (right) shows an example synthesized program of GALOIS (we include more synthesized program examples in Appendix A). E.g. The program specifies the cause of gt_box( () (marked in bold) as the agent has no key and there exists no visible key in the environment. Thus when placed under (oxKey(sem-mod)) GALOIS agent would skip gt. bt_box( and head directly for the key since go_box() is grounded as false by the logic clause body. The result indicates that the explicit use of effect-effeed logic is not only verifiable for humans but allows GALOIS model perform robustly in environments with different task-solving logic. For MPPS, since it only learns fixed sequence of sub-programs it fails to generalize. E.g. synthesized program of MPSS trained on BoxKey is: toggle_bot box () DD:ge__ke gey () :open_dddoo _doo () DDracchhgaae __aallggll (), thus when the key is placed under BoxKey(sem-nnn the agent would follow the learned program and redundantly toggle the box first.
4.4 Knowledge Reusability Analysis (RQ3)
To answer RQ3, we initialize GALOIS model's weights with the knowledge base learned from other tasks (e.g., DeooKey-)Bo and fine-tune the entire model continuously. Figure & shows the detailed results of knowledge reusability among three different environments. Apparently, the learning efficiency can be significantly increased by warm-starting the weights the GALOIS model with knowledge Iearned from different tasks with overlapped logic compared with the one that is

---

DoorKey
BoxKey
DoorKey UnlockPickup
BoxKey - UnlockPickup
Performance
0.6
9.4
0.4
Peeunii Rery wid Likodiiccuu Dea Rog wis
Eooten hovi
0.2
Ecoteptione
200
680
500
1200 1400
200
400
300 1980 1200 1400 #Fiisodes
603
60B M00 #Episodes
#
#Episodes
Figure 8: Knowledge reusability across different environments. full denotes warm- warm-starting policy with the full program, (where, how, what) denotes warm-starting with only the sub-program from the corresponding hole function (e.g., WHERE)) none means learning from scratch.
learned from scratch. Furthermore, we demonstrate the reusability of knowledge from each sub- program, respectively. The results show that considerable boost in learning efficiency can already be obtained by reusing knowledge from each sub-program respectively (e.g., BoakkeyDDooreyyweeea agent is only warm-started with the sub-program of ??HER))) which is an advantage brought by GALOIS's s hierarchical and cause-effect logic. Figure 9 shows an example of knowledge reusing BorKKeeyDoorKy--iiee
from DoorKey to BoxKey environments the DoorKey environment (the orange path in Figure 9). agent only needs to learn the cause-effect logic of toggle_box box () from scratch, which greatly boosts the learning efficiency.
By reusing the logic learned from
Related Work
Neural Program Synthesis: Given set of program specifications (e.g.. I/O examples, natural language instruc- tions, etc.), program synthesis aims induce an explicit program that sat- isfies the given specification. Recent works illustrate that neural networks are effective in boosting both the syn- 6
(a) DoorKey
(b) BoxKey
thesis accuracy and efficiency 12 [8]. Devlin et al. (9) propose using recurrent neural network to synthesize programs for string trans-
Figure The illustration of knowledge reused from DoorKey to BoxKey. The orange path represents the reusable knowl- edge (learned from DoorKey and directly reused in BoxKey).
formation. Chen et al. (6) further proposes incorporating intermediate execution results to augment the model's input state, which significantly improves performance for imperative program synthesis. OILP 12] proposes modeling the forward chaining mechanism with a statistical model to achieve synthesis for Datalog programs.
Many real-world synthesis problems are intractable, posing a great challenge for the synthesis model. Sketching [38 52, 37 is novel program synthesis paradigm that proposes establishing the synergy between the human expert and the synthesizer by embedding domain expert knowledge as general program sketches (i.e., program with unspecified fragments to be synthesized), based on which the synthesis is conducted. Singh al. (37 propose a feedback generation system that automatically synthesizes program correction based on a general program sketch. Nye et al. (25) propose a two-stage neural program synthesis framework that first generates coarse program sketch using neural model, then leverages symbolic search for second-stage fine-tuning based on the generated sketch.
Program Synthesis by Sketching:
Program Synthesis for Reinforcement Learning: Leveraging program synthesis for the good of reinforcement learning has been increasingly popular is demonstrated improve performance and interpretability significantly. Jiang et al. [16] introduce using ØILP model for agent's 's policy, which improves downstream generalization by expressing policy as explicit functional programs. Imperative programs are used novel implementation of hierarchical reinforcement learning in addition, program synthesis
which the agent's policy guided by high-level programs i 1.5]
has also been used post hoc interpretation method for neural policies
412 2

---

6 Conclusion
In this work, we propose novel generalizable logic synthesis framework GALOIS that can synthesize programs with hierarchical and cause-effect logic, A novel sketch-based DSL is introduced to allow hierarchical logic programs. Based on that, a hybrid synthesis method is proposed synthesize programs with generalizable cause-effect logic. Experimental results demonstrate that GALOIS can significantly outperform DRL and previous program-synthen based methods in terms of learning ability, generalizability, and interpretability. Regarding limitation, as it is general for all program synthesis- based methods, the input images need to be pre-processed into Herbrand base for the synthesis model, which is required to be done once for each domain. Therefore, automatic Herbrand base learning would be an important future direction. Another promising direction applying GALOIS in more challenge competitive multi-agent scenarios [50] 14 47 or cooperative multi-agent
scenarios [21 39 49]. impacts.
We state that our work would not produce any potential negative societal
Acknowledgments and Disclosure of Funding
This work is supported by the National Natural Science Foundation of China (Grant No. 62106172. U1836214), New Generation of Artificial Intelligence Science and Technology Major Project of Tian- jin (Grant No.: 19ZXZNGX00010), Science and Technology on Information Systems Engineering Laboratory (Grant No. WDZC200055504007, National Research Foundation, Prime Ministers Office, Singapore under its National Cybersecurity R&D Program (Award No. R122018NCR-NCRR 0001), NRF Investigatorship NRF-NRFI06. 2020-00022000001 the Ministry of Education, Singapore under its Academic Research Fund Tier 1 (21-SIS-SMA SMU-033), Tier 2 (MOE2019-T2-1) T2-1--------00 1-040, and Tier (MOFT32020-0004) Any opinions, findings and conclusions recommendations expressed in this material are those of the author(s) and do not reflect the views of the Ministry of Education, Singapore.
References
Chitta Baral and Michael Gelfond. Logic programming and knowledge representation. The Journal of Logic Programming, 19:73-148, 1994.
[2] Osbert Bastani, Yewen Pu, and Armando Solar-Lezama, Verifiable reinforcement learning via policy extraction. Advances in neural information processing systems, 31, 2018
[3] Rudy Bunel, Matthew Hausknecht, Jacob Devlin, Rishabh Singh. and Pushmeet Kohli. Leveraging grammar and reinforcement learning for neural program synthesis. arXiv preprint arXiv: 1805.04276, 2018.
[4] Samuel R Buss. An introduction to proof theory. Handbook of proof theory, 137:1-78, 1998.
Yushi Cao, Yan Zheng, Shang- Wei Lin, Yang Liu, Yon Shin Teo, Yuxuan Toh, and Vinay Vishnumurthy Adiga. Automatic hmi structure exploration via curiosity-based reinforcement learning. 202/ 36th IEEE/ACM International Conference on Automated Software Engineering (ASE), pages 1151-1155. IEEE, 2021.
[6] Xinyun Chen, Chang Liu, and Dawn Song. Exccution Exccution-guided guided neural program synthesis. In International Conference on Learning Representations, 2018.
[7] Maxime Bhevalier- Lucas Willems, and Suman Pal. Minimalistic gridworld environment for openai gym. https://github. com/ http//axxmmmbbbbc wwwggggmmmiinnni minigrid 2018.
[8] Francis Macdonald Cornford al. The republic Plato. CUP Archive, 1976.
[9] Jacob Devlin, Jonathan Ucsato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. Robustfill: Neural program learning under noisy i/o. In International conference on machine learning, pages 990-998. PMLR, 2017.
[10] Honghua Dong, Jiayuan Mao, Tian Lin, Chong Wang, Lihong Li, and Denny Zhou. Neural logic machines. In 7th International Conference Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenRevicw.net, 2019.
[11] Francesc Esteva and Llus Godo. Monoidal t-norm based logic: towards a logic for loft-cont t-norms. Fuzzy sets and systems, 124(3):271-25) 2001. 2001.
10

---

[12] Richard Evans and Edward Grefenstette. Learning explanatory rules from noisy data. Journal of Artificial Intelligence Research, 61:1-64, 2018.
[13] Tuomas Haarojja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In International conference on machine learning, pages 1861-1870. PMIR, 2018.
[14] Xiaotian Hao, Weixun Wang, Hangyu Mao, Yaodong Yang, Dong Li, Yan Zheng, Zhen Wang, and Jianye Hao. Api: Boosting multi-agent reinforcement learning via agent-permutation- permutaaiooninnvriant networks. arXiv preprint 2203::2203.0228: 2022.
[15] Mohammadhosein Hasanbeig, Natasha Yogananda Jeppu, Alessandro Abate, Tom Melham, and Daniel Kroening- Deepsynth: Automata synthesis for automatic task segmentation deep reinforcement learning. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innova- tive Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pages 7647-7656. AAAI Press. 2021.
[16] Zhengyao Jiang and Shan Luo. Neural logic reinforcement learning. International Conference on Machine Learning, pages 3110-3119. PMLR, 2019.
[17] Kishor Jothimurugan, Rajeev Alur, and Oshert Bastani. A composable specification language for reinforce- ment learning tasks. Advances in Neural Information Processing Systems, 32, 2019.
[18] Armand Joulin and Tomas Mikolov. Inferring algorithmic patterns with stack-augmentedd recurrent nets. Advances in neural information processing systems, 28, 2015.
[19] Daphne Koller, Nir Friedman, Saão Džeroski, Charles Sutton, Andrew McCallum, Avi Pfeffer, Pieter Abbeel, Ming- Fai Wong, Chris Meek, Jennifer Neville, et al. Introduction to statistical relational learning. MIT press, 2007.
[20] Tejas D Kulkarni, Karthik Narasimhan, Ardavan Saeedi, and Josh Tenenbaum. Hierarchical deep reinforce- ment learning: Integrating temporal abstraction and intrinsic motivation. Advances in neural information processing systems, 29, 2016.
[21] Pengyi Li, Hongyao Tang, Tianpei Yang. Xiaotian Hao, Tong Sang. Yan Zheng. Jianye Hao, Matthew Taylor, and Zhen Wang. PMIC: Improving multi-agent reinforcement learning with progressive mutual information collaboration. In International Conference on Machine Learning (ICML). 2022.
[22] Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley. David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International conference on machine learning, pages 1928-1937. PMLR, 2016.
[23] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint 132tv:331
2013.
[24] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 518(7540):52-553 2015.
[25] Maxwell Nye, Luke Hewitt, Joshua Tenenbaum, and Armando Solar- Learning to infer program sketches. In International Conference on Machine Learning, pages 4861-4870. PMIRR 2019.
[26] Judea Pcarl ct al. Models, reasoning and inference. Cambridge, UK: CambridgeeUiivvrsinppresss, 19, 2000.
[27] Athanasios S Polydoros and Lazaros Nalpantidis. Survey of model-based rein learning: Applica- tions robotics. Journal of Intelligent & Robotic Systems, 86(2):153 173, 2017.
[28] Erika Puiutta and Eric Veith. Explainable reinforcement learning: survey. In International cross-domain conference for machine learning and knowledge extraction, pages 77-95. Springer, 2020.
[29] Mukund Raghothaman, Jonathan Mendelson, David Zhao, Mayur Naik, and Bernhard Scholz. Provenance- guided synthesis of datalog programs. Proc. ACM Progrum. Lang., 4(POPL):62-1, 2020.
[30] Frank Rosenblatt. The perceptron: a probabilistic model for information storage and organization in the brain. Psychological review, 65(6))386, 1958.

---

[31] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
[32] Dana S Scott and Christopher Strachey, Toward mathematical semanties for computer languages. volume Oxford University Computing Laboratory, Programming Research Group Oxford, 1971.
[33] Dhruv Shah, Alexander T Toshev, Sergey Levine, and brian ichter. Value function spaces: Skill-centric state abstractions for long-horizon reasoning. In International Conference on Learning Representations, 2022.
[34] Dhruv Shah, Peng Xu, Yao Lu, Ted Xiao, Alexander T Toshev, Sergey Levine, et al. Value function spaces: Skill-centric state ahstractions for long-horizon reasoning. In Deep RI. Workshop NeurlPS 2021, 2021.
[35] Ruimin Shen, Yan Zheng, Jianye Hao, Zhaopeng Meng, Yingfeng Chen, Changjie Fan, and Yang Liu. Generating Salavor-diverrs game ais with evolutionary multi-objective deep reinforcement learning. In IJCAI, pages 3371-3377 00773,37,0000 2020.
[36] Xujie Si, Woosuk Lee, Richard Zhang, Aws Albarghouthi, Paraschos Koutris, and Mayur Naik. Syntax- guided synthesis of datalog programs. In Proceedings the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, pages 515-527, 2018.
[37] Rishabh Singh, Sumit Gulwani, and Armando Solar-Lezama, Automated feedback generation for introduc- tory programming assignments. In Proceddings of the 34th ACM SIGPIAN conference on Programming language design and implementation, pages 15-26, 2013.
[38]
Armando Solar-Lezama, Program synthesis by sketching. University of California, Berkeley, 2008
[39] Jianwen Sun, Yan Zheng. Jianye Hao, Zhaopeng Meng, and Yang Liu. Continuous multiagent control using collective behavior entropy for large-scale home energy management. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 922-929, 2020.
[40] Shao-Hua Sun, Te-Lin Wu, and Joseph Lim. Program guided agent. In International Conference on Learning Reprexentations, 2019.
[41] Abhinav Verma, Vijayaraghavan Murali, Rishabh Singh, Pushmeet Kohli, and Swarat Chaudhuri. Pro- grammatically interpretable reinforcement learning. In International Conference on Machine Learning, pages 5045-5054. PMLR, 2018.
[42] Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8(3):229-25) 256, 1992.
[43] Patrick Henry Winston. Artificial intelligence. Addison-Wesley Longman Publishing Co., Inc., 1992.
[44] Yichen Yang, Jeevana Priya Inala, Osbert Bastani, Yewen Pu, Armando Solar-Lezama, and Martin Rinard. Program synthesis guided reinforcement learning for partially observed environments. Advances in Neural Information Processing Systems, 34, 2021.
[45] Philipp Zech, Simon Haller, Safoura Rezapour Lakani, Barry Ridge, Emre Ugur, and Justus Piater. Computational models of affordance in robotics: a taxonomy and systematic classification. Adaptive Behavior, 23(5):235-271, 2017.
[46] Peng Zhang, Jianye Hao. Weixun Wang, Hongyao Tang. Yi Ma. Yihai Duan, and Yan Zheng. KoGuN: Accelerating deep reinforcement learning via integrating human suboptimal knowledge. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (ICCAI), pages 2291-2297, 2020.
[47] Yan Zheng, Jianye Hao, Zongzhang Zhang, Zhaopeng Meng, Tianpei Yang, Yanran Li, and Changjie Fan. Efficient policy detecting and reusing for non-stationarity in markov games. Autonomous Agents and Multi-Agen Systems, 35(1):1 29, 2021.
[48] Yan Zheng, Liu, Xiaofei Xic, Yepang Liu, Lei Ma, Jianye Hao, and Yang Liu. Automatic web testing using curiosity-driven reinforcement learning. In 202/ IEEE/ACM 43rd International Conference on Software Engineering (ICSE), pages 423-435. IEEE, 2021.
[49] Yan Zheng, Zhaopeng Meng, Jianye Hao, and Zongzhang Zhang. Weighted double deep multiagent reinforeement learning in stochastic cooperative environments. In Pacific Rim international conference on artificial intelligence, pages 421 -299. Springer, 2018.
12

---

[50] Yan Zheng, Zhaopeng Meng, Jianye Hao, Zongzhang Zhang, Tianpei Yang, and Changjie Fan. A deep bayesian policy reuse approach against non-stationary agents (neurips). In Advances Neural Information Processing Systems, volume 31, 2018.
[51] Yan Zheng, Xiaofei Xie, Ting Su, Lei Ma. Jianye Hao. Zhaopeng Meng. Yang Liu, Ruimin Shen, Yingfeng Chen, and Changjie Fan. Wuji: Automatic online combat game testing using evolutionary deep reinforcement learning. In 2019 34th JEEE/ACM International Conference on Automated Software Engineering (ASE), pages 772-784. IEEE, 2019.
[52] He Zhu, Zikang Xiong, Stephen Magill, and Suresh Jagannathan. An inductive synthesis framework for verifiable reinforcement learning. In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 686-701, 2019.
13

---

Checklist
1. For all authors...
(a) Do the main claims made the abstract and introduction accurately reflect the paper's contribu- tions and scope? [Yes]
(b) Did you describe the limitations your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material URL)? [Yes] See Section
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Ye]] See Appendix
(c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [Yes] See Section
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix
4. If you using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) your work uses existing assets, you cite the creators? [Yes]
(h) Did you mention the license of the assets? [Yes]
(c) Did you include any
either in the supplemental material URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're 'r us-
ing/curating? [N/A]
(c) Did you discuss whether the data you using/curating contains personally identifiable informa- tion offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable?
[N/A]
(b) you describe any potential participant risks, with links to Institutional Review Board (IRB)
approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "xj2KyjreKU", "reviewer": "Reviewer_WqvU", "summary": "GALOIS introduces a DSL synthesis framework for reinforcement learning that combines both imperative and declarative programs. \nIt 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. \nThe contributions of this paper include:\n1. A new domain-specific language for synthesizing a hierarchical program\n2. A synthesize algorithm of this DSL\n3. Evaluations comparing GALOIS and various baselines, showing GALOIS has better performance.", "questions": "1. Can you explain more about the predicate deduction process, and the $normalized weighted vector $\\theta_\\rho^\\psi$?\n2. Can you explain the user interface on the framework. The user requires to provide the ICFG, but what about the head nodes?\n3. In general, how is the action space incorporated into the program synthesis process?\n4. It would be helpful to include another environment to demonstrate adaptability as a general framework. ", "limitations": "The authors addressed the limitations of this approach.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: 3/5 \n\nThe 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.\n\nQuality: 3/5\n\nPros:\n1. This paper shows a variety of baseline comparisons on the box task.\nCons:\n1. The environment only has the \"box-world\" environment evaluation, but not another one.\n     a) What are the user input and difficulties to adapt this approach to another setup?\n     b) Performance comparison (minor)\n\nClarity: 2.5/5\n\nPros: The intuition and $DSL_{hybrid}$ are explained pretty clearly.\nCons:\n1. The formalization is not clear enough. Specifically,\n    a) How is the action space incorporate into the program synthesis is not clear in the formalization.\n    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?\n    c) Can you explain more about the \"normalized weighted vector $\\theta_\\rho^\\psi$?\n    d) It would help a lot to include a running example \n\nSignificance: 3/5\nThis approach performs much better than both the pure neural approach and the current program synthesis approach. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "vsepat1_bU", "reviewer": "Reviewer_sTbQ", "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.", "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.\n\n2. 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.\n\n3. 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.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nWhile 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.\n\n1. 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.\n\n2. 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.\n\n3. How would GALOIS work on other benchmarks, e.g., those evaluated in the MPPS paper?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Spj80rqXv5e", "reviewer": "Reviewer_aGFV", "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. ", "questions": "Summarizing some points expressed above:\n\n- Which are the functions, namely the A set, available to both GALOIS and the baselines?\n- 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.\n- Which is the DSL used by the neural baselines?\n- 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?\n- How do you collect the train experiences for GALOIS? Do you run a partial sketch and do you keep only the successful trajectories? \n- How is a GALOIS policy defined (see equation line 215)?\n", "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.\n\nLastly, 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.\n\n[1] Pearl, Judea. Causality. Cambridge university press, 2009.\n\n[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.\n", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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. \n\nI 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. \n\nProgram-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. \n\nOn 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.\n\nI 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. \n\nMoreover, 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. \n\nMinor issues:\n\nLine 43: programs … have limited generalizability\n\nLine 94: a procedure defined based…\n\nLine 339: prorgam-synthesis —> program-synthesis", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept