Embedded Files
Introduction
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.
Methodology
Figure 1
Figure 1 shows the overview of the GALOIS framework, where the (a) sketch-based DSL defines what program can be synthesized, and (b) sketch-based ILP synthesizes programs with logic. First, to synthesize logic programs with both hierarchical logic and explicit cause-effect logic, we design a novel sketch-based DSL, namely L_{hybrid}, absorbing both the advantages of imperative and declarative programming. Figure 1 shows the detailed syntax and semantic specifications of L_{hybrid}. It is noteworthy that L_{hybrid} ensures the synthesized program follows strict cause-effect logic. Beyond that, following L_{hybrid}, 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. Second, different from the black-box model, \alg requires different types of input and output. Therefore, \alg maintains an encoder E and a decoder D to interact with the environment. E(s) maps the state s to a set of ground atoms (formatted as valuation vector e_\ rho) with the verification from L_{hybrid}, i.e., e = E(s, L_{hybrid}). As shown in Figure 1(b), the leftmost squares with different colors represent the atoms from different hole functions (e.g. blue squares f_{1,t}_{t=1}^m denotes the ground atoms for ??_{WHERE}). Based on e_\rho, GALOIS outputs a predicate and a = D(e_\rho) decodes it into the corresponding action in the environment, where p denotes the deduction process.
Page updated
Google Sites
Report abuse