Deep reinforcement learning has obtained impressive results in the last few years. However, the limitations of deep reinforcement learning with respect to interpretability and generalization have been clearly identified and discussed. In order to overcome these limitations, neural-symbolic methods for reinforcement learning have been recently proposed. This paper presents preliminary results on a new neural-symbolic method for reinforcement learning called State-Driven Neural Logic Reinforcement Learning. The discussed method generates sets of candidate logic rules directly from the states of the environment. Then, it uses a diferentiable architecture to select a good subset of the generated rules to successfully complete the training task. The experimental results presented in this paper provide empirical evidence that the discussed method can achieve good performance without requiring the user to specify the structure of the generated rules. Besides being preliminary, the experimental results also suggest that the presented method has suficient generalization capabilities to allow using learned rules in environments that are suficiently similar to the training environment. However, this is a preliminary work, and the experimental results show that the proposed method is not yet suficiently efective.
Deep reinforcement learning has received increasing interest from the research community
in recent years because its methods have obtained impressive results on many complex tasks
(e.g., [
In order to overcome these two major limitations, neural-symbolic methods for reinforcement
learning have gained relevant interest and appreciation. Many research proposals have tried
to combine neural approaches with first-order logic, such as DLM [
This paper proposes a novel neural-symbolic method for reinforcement learning, called
SD-NLRL (State-Driven Neural Logic Reinforcement Learning), that is largely based on NLRL.
For a given learning task, NLRL generates a set of candidate rules using a top-down approach
that requires the user to specify a set of hyper-parameters, called program template, to guide
the generation of rules. On the contrary, SD-NLRL generates its candidate rules directly from
the states of the environment. Actually, SD-NLRL uses a modified version of the diferentiable
architecture of NLRL to select the best subset of the generated rules that solves the task under
investigation. In order to fairly compare SD-NLRL with NLRL, SD-NLRL was used on the
tasks that are described in the paper [
The work presented in this paper is closely related to relational reinforcement learning [
A recent work on neural-symbolic reinforcement learning that is closely related to SD-NLRL
is documented in [
Another method that is closely related to SD-NLRL is DLM [
The remaining of this paper is structured as follows. Section 2 discusses the proposed method. Section 3 presents an experimental comparison of SD-NLRL and NLRL. Finally, Section 4 concludes this paper discussing some of the current limitations of SD-NLRL and outlining possible research directions for the future.
The first part of this section presents a brief recall of the subset of first-order logic, namely
Datalog, that is considered in this work. Then, this section proceeds with a brief introduction
to NLRL, which is the neural-symbolic method for reinforcement learning that represents the
base of SD-NLRL. Finally, SD-NLRL is described focusing on its main diferences from NLRL.
Datalog is a subset of first-order logic, and its syntax comprises three main primitives: predicate
symbols, variable symbols, and constant symbols. Predicate symbols, or predicates, represent
relations among objects in the domain of discourse. Constant symbols, or constants, represent
the objects of the domain of discourse. Variable symbols, or variables, represent references to
unspecified objects of the domain of discourse. An atom is defined as ( 1, … , ), where is a
predicate and 1, … , are terms, which can be either variables or constants. For example, if on(X,
table) is an atom that is true if the first object is on the second object, then on is the predicate
symbol, is a variable, and table is a constant. When the terms 1, … , are all constants, the
atom is called ground. A rule in the form ← 1, … , is called definite clause. For the sake of
simplicity, in this work, the word rule is considered as a synonym of definite clause. When a
predicate is defined using ground atoms only, it is called extensional predicate. On the contrary,
when a predicate is defined using a set of definite clauses, it is called intensional predicate.
2.2. NLRL
NLRL is an adaptation for reinforcement learning tasks of ILP [
In order to solve a reinforcement learning task, NLRL associates a trainable weight with each
generated rule. In particular, NLRL defines a valuation vector in = [
, (),
0≤≤ 0≤≤ the -th rule generated from the -th rule template for predicate .
where is the number of rule templates that define predicate , is the number of rules generated from the -th rule template, , is the trainable weight associated with the -th rule generated from the -th rule template for predicate , and ℎ, () represents a single deduction step using
For a given learning task, NLRL generates a set of candidate rules for each rule template, but only one rule can be selected for each rule template. Therefore, each weight , is obtained by applying a softmax function to the underlying vector of weights : , = softmax ( )[].
1 = gather(, 1 ) 2 = gather(, 2).
(2) (3) (4) (5) (6) (7) Given a rule , each function ℎ ∶ →
takes a valuation representing the truth value of the ground atoms and computes a valuation that represents the truth value of the atoms resulting from the application of the rule. For each function ℎ , NLRL builds the following matrix : = {(, ) | satisfies ( , ) ∧ head ( , ) = }, where is a set of pairs of indexes, and each pair refers to two ground atoms that entail the ground atom of index . Each matrix is a × × 2 matrix, where is the maximum number of ground atoms that entail each ground atom. It is worth noting that the unused index pair (0, 0) must reference to a pair of atoms. Therefore, NLRL introduces the falsum atom ⊥ in , and it maps (0, 0) to (⊥, ⊥). In order to perform the forward chaining steps during the training phase, NLRL computes two slices of , namely 1, 2 ∈ ℕ× , as: 1 = [_, _, 0] 2 = [_, _, 1]. gather ∶ × ℕ ×
→ ℝ× as follows:
NLRL retrieves the actual truth values of each ground atom to obtain 1, 2 ∈ [
= 1 ⊙ 2.
Finally, NLRL defines ℎ () as: ℎ () = ′ where ′[] = max [, ] 1≤≤ Note that the maximum operator implements fuzzy disjunction while element-wise multiplication provides for fuzzy conjunction.
In order to generate a set of suitable candidate rules to solve a reinforcement learning task, NLRL requires the user to specify a large amount of data about the structure of the solution. On the contrary, SD-NLRL requires the complete set of possible states, and it automatically generates a set of abstract rules that can represent the solutions of the learning task.
The rule generation process that characterizes SD-NLRL is described as the g e n e r a t e _ r u l e s function in Algorithm 1. This function requires the set of possible action atoms , the set of possible states , and the set of background atoms . The function subdivides each state into a set of groups using the g e t _ g r o u p s function. Each group contains a subset of the state, and each atom in a group is, directly or indirectly, connected with the other atoms in the same group through its constants. Therefore, diferent groups have diferent constant sets, and each group represents a feature of the state that contributes to the truth value of the action predicate. Then, for each pair of group and action, the g e n e r a t e _ r u l e s function retrieves the constants that are shared between the action atom and the group using the g e t _ s h a r e d function. The g e n e r a t e _ r u l e s function inserts into the group the background atoms that include at least one shared constant. In fact, the shared constants are the most significant constants because they relate the features of the state with the action to be taken. Then, g e n e r a t e _ r u l e s function computes, using the g e t _ f r e e function, the set of free constants, which are the constants that are not shared between the action atom and the group after the inclusion of the related background atoms. If the set of free constants is empty, the g e n e r a t e _ r u l e s function computes the final rules using the u n g r o u n d function, which transforms each ground term of the rule into a corresponding variable. Otherwise, the function produces a rule for each free constant. In particular, the function transforms the free constants that are diferent from the one taken in consideration. Then, it includes in the body of the generated rule the background atoms that contain the considered free constant. Finally, the u n g r o u n d function transforms the remaining constants in the rule into variables. The generation of a new rule for each free constant is useful to reduce the complexity of each rule. In fact, the goal of the function is to extract the most simple features from each state and let the diferentiable architecture select the most appropriate subset of the rules that is capable to solve the learning task. The u n g r o u n d function starts from the body of the rule given as second argument, and it proceeds from left to right. Then, it transforms the head of the rule given as first argument. The third argument of the u n g r o u n d function is a set of constants. If the set is not empty, the function transforms only the constants that are included in this set.
Algorithm 1 The function that performs the generation of rules in SD-NLRL 1: function generate_rules(, ,
) rules ← {} for each ∈ do ←
get_groups() for each ∈
do for each ∈
do
ensure that the weights are in [
(), 0≤≤ as:
=
max( ) − max( ) − min( ) . (10) Moreover, the definition of the deduction step, represented by ℎ () , has been coherently modified in SD-NLRL. In particular, SD-NLRL defines a matrix called , as follows: ∈ ℕ×× for each rule SD-NLRL builds the matrices 1, … , ∈ ℕ× before the training phase, where represents the -th element of the body of the rule . Then, SD-NLRL obtains the matrices 1, … , ∈ ℝ× using the gather function. These matrices are used to build the matrix as: = 1 ⊙ ⋯ ⊙ .
Finally, SD-NLRL defines
ℎ () in the same way as NLRL does.
The weight normalization rule that SD-NLRL uses allows an action predicate to be defined by multiple rules. In particular, each weight depends only on the minimum weight and on the maximum weight defined for the predicate. Therefore, SD-NLRL can associate the same weight with diferent rules. However, the adopted normalization technique does not work well when SD-NLRL generates only one rule for an action predicate. Moreover, this normalization technique implies that a rule with weight 0 and a rule with weight 1 are always learned, which can prevent SD-NLRL from learning the optimal strategy in some cases. (12) (13)
In order to assess the performance of SD-NLRL, the proposed method has been used on the
reinforcement learning tasks that are discussed in [
Note that, as previously discussed, SD-NLRL tries to subdivide each state into disjoint groups of atoms, but the states of block manipulation tasks are composed of densely connected atoms. Therefore, SD-NLRL generates a large number of complex rules. Unfortunately, the required computational resources increase considerably as the size of the rules and the number of rules increase. Therefore, SD-NLRL fails to complete the training phases of the block manipulation tasks, and only the clif-walking tasks are discussed in the remaining of this section.
The implementation of SD-NLRL is based on the oficial implementation of NLRL 1. In particular, the implementation of SD-NLRL and the implementation of NLRL share the same 1github.com/ZhengyaoJiang/NLRL hyper-parameters. The only exceptions are the learning rate and the number of deduction steps. The learning rate of SD-NLRL was set to 0.0005 and 0.0001 for CLIFFWALKING and WINDYCLIFFWALKING, respectively. The number of deduction steps of SD-NLRL was set to 1 for both tasks because a single forward chaining step is suficient to obtain the correct truth values of the action predicates.
Table 1 shows the performance of SD-NLRL for the two considered clif-walking tasks. The
results shown in Table 1 were obtained performing 5 runs for each task, and each trained model
was evaluated on 100 episodes for each task. Then, the results were averaged over all runs. In
order to evaluate the generalization capabilities of SD-NLRL, the trained models were tested on
other tasks that are slightly diferent from the ones used for training. In particular, the algorithm
was evaluated on the same tasks discussed in [
The results reported in Table 1 show that SD-NLRL is able to learn an efective strategy that solves CLIFFWALKING. Moreover, the learned model is able to generalize to diferent tasks. However, the results sufers from great variance. In fact, in 1 of 5 five trials, SD-NLRL learned a strategy that is only able to occasionally get a positive reward. In particular, when the agent does not succeed to quickly learn a good strategy, it remains trapped in a local optimum and stops learning. The results for WINDYCLIFFWALKING show even worse performance, and SD-NLRL consistently fails to learn a good strategy. The algorithm learns over time, but the learning speed is very slow, and it always remains trapped in a local optimum. This behavior is explained by the fact that in NLRL rules are generated from a carefully hand-crafted program template. On the contrary, SD-NLRL automatically generates the rules from the states of the environment, trying to limit both the size and the number of generated rules. Therefore, SD-NLRL does not succeed in generating the best rules for each action predicate. Both these problems represent interesting challenges for the future.
In order to ofer a comprehensive view on SD-NLRL, the learned rules that obtain the best performance in the CLIFFWALKING task (on the right) with their corresponding weights (on the left) are reported: The learned rules represent an efective strategy, and the agent obtains high returns on the training environment (0.844 ± 0.034). However, the learned strategy is not compact, and some rules are unnecessary. For example, the last two rule defined for r i g h t ( ) and the last rule defined for u p ( ) can be safely omitted. SD-NLRL generates the rules directly from the states of the environment, and many generated rules are unnecessary or even harmful and they should be avoided. Therefore, an interesting research direction for the future regards the reduction of unnecessary rules either refining the rule generation process or introducing a penalization for redundant rules. It is worth noting that the only rule learned for l e f t ( ) can compromise the performance of the strategy because the agent often moves left before moving up. Therefore, the learning of strategies when actions are forbidden should be further investigated. Finally, the learned rules, together with their weights, that obtain the worst performance in the CLIFFWALKING task are reported for completeness: d o w n ( ) : - c u r r e n t ( Y , X ) , l a s t ( Y ) , s u c c ( Z , Y ) . l e f t ( ) : - c u r r e n t ( X , Y ) , s u c c ( Y , Z ) , z e r o ( Y ) . r i g h t ( ) : - c u r r e n t ( Y , X ) , s u c c ( Z , Y ) , s u c c ( Y , M ) . r i g h t ( ) : - c u r r e n t ( X , Y ) , s u c c ( Z , Y ) , s u c c ( Y , M ) . r i g h t ( ) : - c u r r e n t ( X , Y ) , l a s t ( Y ) , s u c c ( Z , Y ) . r i g h t ( ) : - c u r r e n t ( X , X ) , s u c c ( Y , X ) , s u c c ( X , Z ) . u p ( ) : - c u r r e n t ( X , X ) , s u c c ( X , Y ) , z e r o ( X ) . u p ( ) : - c u r r e n t ( X , X ) , l a s t ( X ) , s u c c ( Y , X ) . d o w n ( ) : - c u r r e n t ( X , X ) , l a s t ( X ) , s u c c ( Y , X ) . d o w n ( ) : - c u r r e n t ( Y , X ) , l a s t ( Y ) , s u c c ( Z , Y ) . d o w n ( ) : - c u r r e n t ( X , X ) , s u c c ( Y , X ) , s u c c ( X , Z ) . d o w n ( ) : - c u r r e n t ( X , Y ) , s u c c ( Y , Z ) , z e r o ( Y ) . l e f t ( ) : - c u r r e n t ( X , X ) , s u c c ( X , Y ) , z e r o ( X ) . l e f t ( ) : - c u r r e n t ( Y , X ) , s u c c ( Z , Y ) , s u c c ( Y , M ) . r i g h t ( ) : - c u r r e n t ( Y , X ) , s u c c ( Z , Y ) , s u c c ( Y , M ) . r i g h t ( ) : - c u r r e n t ( X , X ) , l a s t ( X ) , s u c c ( Y , X ) . r i g h t ( ) : - c u r r e n t ( X , Y ) , l a s t ( Y ) , s u c c ( Z , Y ) . r i g h t ( ) : - c u r r e n t ( X , X ) , s u c c ( Y , X ) , s u c c ( X , Z ) . u p ( ) : - c u r r e n t ( X , Y ) , s u c c ( Y , Z ) , z e r o ( Y ) . u p ( ) : - c u r r e n t ( Y , X ) , s u c c ( Y , Z ) , z e r o ( Y ) .
u p ( ) : - c u r r e n t ( X , X ) , s u c c ( Y , X ) , s u c c ( X , Z ) .
In this case, the number of learned rules is higher, and the agent obtains low returns in the training environment (0.154 ± 0.629). In fact, many rules are unnecessary or even wrong. Note that, in both cases, only the rules with a weight greater than 0.3 are shown for space limitations.
From the point of view of the required computational resources, SD-NLRL drastically reduces the number of generated rules with respect to NLRL. Moreover, SD-NLRL performs only 1 deduction step, thus further reducing the required computational resources. In fact, NLRL generates 2813 rules for the clif-walking tasks, while SD-NLRL generates only 36 rules for the same tasks. The number of generated rules directly influences the required amount of computational resources. Actually, NLRL requires approximately 10 days to complete a training process, while SD-NLRL complete a training process in less than 2 hours. The required memory is reduced as well. SD-NLRL uses approximately 1.6Gb, while NLRL uses approximately 17Gb. These results are preliminary, and a complete analysis of the computational resources that SD-NLRL requires is left for the future. However, it is worth noting that SD-NLRL does not always reduce the required computational resources because it struggle with densely connected states. In fact, in many cases, SD-NLRL generates a large amount of complex rules because it does not limit the size and the number of generated rules. Therefore, the generation of compact and abstract rules even in worst cases represents an important direction for future research.
This paper introduced a novel neural-symbolic method for reinforcement learning called SD-NLRL. The proposed method is based on NLRL, but it generates candidate rules directly from the states of the environment. The experimental results discussed in the final part of this paper show that the proposed method is able to efectively learn a good strategy in one of the clif-walking tasks, and that the method is also able to generalize this strategy to tasks that are slightly diferent from the one used for training. However, SD-NLRL fails to solve block manipulation tasks because it is not able to generate compact rules from the densely connected states that characterize these tasks. The generation of compact, yet general, rules from densely connected states represents an important challenge for the future. Moreover, SD-NLRL often remains trapped in local optima, and this is unquestionably evident when the dificulty of the task under investigation increases. Another important challenge for the future is to make SDNLRL more robust against the traps represented by local optima. In addition, the analysis of the learned rules suggests that: SD-NLRL learns many unnecessary rules, and it is not able to learn an efective strategy when an action is forbidden. Both these problems are two other relevant challenges for the future. Finally, the assumption that the environment is able to provide the set of all possible states represents another important limitation of SD-NLRL. Therefore, a relevant improvement of the method regards the design of an iterative rule-generation process in which new rules are generated only when new states are encountered. In summary, this is a preliminary work, and the current form of the proposed method cannot be considered competitive with other neural-symbolic methods for reinforcement learning like NLRL. However, the presented experimental results are encouraging, and an improved version of SD-NLRL can be considered as a viable means toward efective neural-symbolic reinforcement learning.