Deduction with Induction: Combining Knowledge Discovery and Reasoning for Interpretable Deep Reinforcement Learning

1 Introduction

In recent years, deep reinforcement learning (DRL) [Mnih et al., 2015] has gained widespread popularity due to its successful implementation in a variety of dynamic decisionmaking tasks [Zhang et al., 2022; Vinyals et al., 2019; Kulkarni et al., 2016; Wang et al., 2016]. This shift in paradigm is largely fueled by the capability of deep models to autonomously acquire sophisticated behaviors and strategies through interaction with complex environments. However, one of the major limitations of DRL is its lack of interpretability, which creates substantial barriers to understanding and explaining how these models make decisions. Interpretability plays a crucial role in decision-making systems, serving as a bridge between the model's underlying mechanics and human cognitive processes [Gilpin et al., 2018; Ibarz et al., 2018]. Without interpretability, the models become opaque, limiting their transparency, accountability, and user trust. This lack of clarity makes it challenging to trace the model's decision-making process or enhance it with more interpretable knowledge. The issue is particularly problematic during the early training phases, where models tend to perform poorly and learn inefficiently, a situation commonly referred to as the "cold start" problem [Mnih et al., 2015].

There have been many attempts to imbue DRL with interpretability. Some of them provide manually designed rules for high-level planning with pre-defined subtasks. For instance, SDRL [Lyu et al., 2019] employs hierarchical reinforcement learning with two layers, namely, the high-level and low-level layers. The high-level layer distributes predefined subtasks, while the low-level layer interacts with the environment according to the high-level tasks. Hierarchical reinforcement learning is particularly effective for learning environments with sparse rewards, where higher layers can provide intrinsic rewards based on task completion. Another related work SORL [Jin et al., 2022] require manual provision of more complex action model. Some other work utilizes symbolic knowledge as a post-hoc explanation for the trained DRL models, aimed at unveiling the reasoning behind DRL decisions [Ma et al., 2021]. For instance, NSRL [Ma et al., 2021] provides a automated symbolic knowledge discovery for DRL. The method generates chained first-order logic rules without the need for manually designing templates, thereby improving flexibility and saving manpower. While efforts have been made to improve the interpretability of DRL models, the post-hoc explanation is only helpful for understanding the trained deep models, without further utilizing the extracted knowledge for better decision making.

The above existing attempts to imbue DRL with interpretability either integrates symbolic discovery as an explanatory tool post-hoc, or involves manually injecting symbolic knowledge into DRL models. The former fails to integrate the extracted knowledge into the decision process, and the latter demands considerable human effort and limits the flexibility of the DRL system to adapt and generalize to diverse environments. In this paper, we argue that the knowledge discovery and reasoning can be combined and integrated into the process of the DRL training. With the explorations and interactions between the agent and the environment, useful high-level knowledge is extracted and subsequently utilized to make a potentially better decision. With iterative exploration and training, the extracted knowledge becomes more accurate, and meanwhile the deep model achieves better performance in decision making. To achieve that, we propose in this paper a novel neural-symbolic framework that leverages ad-hoc knowledge discovery and reasoning for interpretable deep reinforcement learning. Our work begins to utilize rules in the process of rule generation to accelerate the learning process of the model itself. In addition, we hope that the rules generated with a specific domain can be generalized and transferred to other domains. To this end, we construct new algorithms that provide the agent with potentially generally applicable rules from the beginning and apply these rules appropriately, which our research shows can speed up learning. We highlight our contributions in the following areas.

1. We introduce a novel neural-symbolic framework, Hierarchical Reinforcement Learning with Automated Knowledge Induction and Deduction (HRL-ID 1 ), which integrates symbolic knowledge representation and reasoning into hierarchical deep reinforcement learning.
2. Our approach combines knowledge discovery and reasoning to provide interpretable deep reinforcement learning. The symbolic knowledge extracted by HRLID not only offers a clear explanation for DRL but also enhances learning efficiency during training.
3. We conduct a series of experiments that show HRL-ID outperforms existing state-of-the-art methods in both interpretability and learning efficiency.

2 RelatedWork

Deep reinforcement learning (DRL) has made significant advancements in a variety of applications, with widely used algorithms such as DQN, Dueling DQN, and Double DQN [Mnih et al., 2013; Wang et al., 2016; van Hasselt et al., 2016] gaining broad recognition. Despite this success, concerns about the interpretability and data efficiency of deep learning models in the realm of DRL have surfaced. To address these concerns, recent research endeavors have been dedicated to enhancing the interpretability of DRL models.

Numerous strategies have emerged to bolster the interpretability of DRL. This terrain can be broadly classified into two overarching approaches: self-explanation and postinterpretation. The self-explanation approach centers on imbuing the model with self-awareness and the capacity to elucidate its own behavior. As illustrated by the aforementioned SDRL method, this approach incorporates a self-contained transformation model interpretation strategy. In tandem, a separate line of investigation revolves around the acquisition of strategies through imitation learning. Scholars have diligently explored techniques for cultivating interpretable strategies [Verma et al., 2019; Bastani et al., 2018].

Conversely, post-hoc interpretation methods rely on auxiliary models or techniques to facilitate the interpretation of trained DRL models [Juozapaitis et al., 2019; Madumal et al., 2020; Rusu et al., 2016; Hayes and Shah, 2017]. This paradigm aims to unveil the decision-making processes underpinning the model's behavior. Illustrative instances of these methods encompass the utilization of saliency maps and proxies for DRL interpretation [Puri et al., 2020; Zahavy et al., 2016; Greydanus et al., 2018]. Typically, these techniques engender visualizations or evaluate the significance of diverse input features to unravel the model's conduct.

Furthermore, there exists a category of methods that harness rule-assisted models, exemplified by HIRL [Gao et al.,

1 https://github.com/ResearchGroupHdZhang/HRL-ID

2020; Saunders et al., 2018]. In this context, pre-defined human-crafted rules are seamlessly integrated to steer the learning trajectory. Nonetheless, these methodologies often necessitate human intervention and manual rule stipulation to attain interpretability.

While these endeavors have made noteworthy strides in augmenting the interpretability of DRL and HRL, they often do not fully exploit the potential of extracted models to augment training efficiency. Our work exploits extracted explanations to speed up training and facilitate rule generalization in various contexts of the same game as well as different games.

3 Method

We formally introduce our method, Hierarchical Reinforcement Learning with automated knowledge Induction and Deduction (HRL-ID). Figure 1 illustrates the comprehensive framework of HRL-ID, highlighting the integration of rule induction and reasoning within a hierarchical reinforcement learning structure.

HRL-ID synergizes hierarchical reinforcement learning with neural-symbolic reasoning to enhance both interpretability and learning efficiency. The system comprises three core components:

1. Rule Generation and Update: Facilitates the induction of logical rules from environmental interactions and their continual refinement.
2. Rule Matching and Reasoning: Utilizes the induced rules to guide decision-making through rule-based policy generation.
3. Knowledge Generalization and Grounding: Ensures the transferability and generalization of rules across different environments.

3.1 Rule Generation and Update

The Rule Generation and Update process is a fundamental component of HRL-ID, facilitating the dynamic creation and refinement of logical rules based on interactions within the environment. This process is divided into three key submodules: the Attention Submodule, the Integration Submodule, and the Policy Submodule.

Attention Submodule

The Attention Submodule leverages a hierarchical transformer architecture to dynamically compute attention scores for predicates and relational paths. By employing the MultiHead Dot-Product Attention mechanism [Vaswani, 2017], it processes the symbolic state tensor X ∈ [0, 1]|B|×|B|×N , where B represents the entity set and N represents the predicate set.

Predicate Attention This module generates the attention score Aα of the predicate at the time step. The symbolic state tensor X is reshaped into a matrix Xr ∈ [0, 1]|B|2×N , where each row corresponds to the embedding of a predicate. The attention mechanism is applied iteratively as follows:

where FFN(k) represents the feedforward network at time step k, and S(k) λ are the attention weights for predicates at step k.

Path Attention The Path Attention Submodule is responsible for computing attention scores Sθ for logical rules of various lengths, aggregating information across steps:

where Vλ = [V (0) , V (1) , . . . , V (T) ] concatenates the outputs from all steps.

Integration Submodule

The Integration Submodule is inspired by multi-hop reasoning mechanisms in knowledge graphs, enabling the agent to infer complex relationships via sequential predicate applications. In a knowledge graph, entities are represented as nodes, while predicates serve as edges. The multi-hop process seeks to uncover chain-like logical rules expressed as:

In this setup, Ri denotes predicates that define relationships between entities. The relationship between predicates is represented as successive matrix multiplications, where each predicate Pk is modeled as a binary matrix Mk ∈ {0, 1}|A|×|A| , with Mk(i, j) = 1 indicating the presence of the predicate Pk between entities ai and aj .

The multi-hop reasoning is computed as:

To incorporate attention over different predicates and paths, the final score is refined using soft attention:

where κ(Sθ, Sλ) represents the combined attention scores for predicates and paths generated by the Attention Submodule.

Policy Submodule

The Policy Submodule determines the actionable strategy within the hierarchical reinforcement learning framework based on the outputs of the Integration Submodule. The predicate set Q includes both state predicates Qs and action predicates Qa. Each action predicate Actq(a, a′ ) ∈ Qa corresponds to a potential action.

For each action predicate Actq, a Multi-Layer Perceptron (MLP) MLPq is used to compute the state-action value:

Rule Update To ensure the relevance and accuracy of the induced rules, HRL-ID employs a success rate-based refinement mechanism. The success rate of each rule's corresponding sub-goal is tracked, and significant deviations in success rates trigger rule updates:

∆sr = current success rate - previous success rate

If |∆sr| > δupdate, where δupdate is a predefined threshold, the rule set R is updated by extracting new rules from the accumulated game states S:

This dynamic rule update ensures that the rule set remains aligned with the agent's evolving understanding of the environment, thereby enhancing learning efficiency and decisionmaking accuracy.

Algorithm 1 HRL-ID Algorithm

Input: General knowledge base Rin (could be empty), rule

update threshold δupdate, number of episodes T

• 1: Initialize:
• 2: Rule set R←Rin (if provided)
• 3: Game state set S ← ∅
• 4: Abstract rule mapping set Am ← ∅
• 5: Model parameters θ
• 6: Success rate list sr ← ∅
• 7: if Rin is not empty then
• 8: Rgrd = RuleGrounding(Rin,Am)
• 9: R←R∪Rgrd
• 10: end if
• 11: for each episode = 1 to T do
• 12: Initialize game environment, obtain initial state S0
• 13: Initialize success rates for sub-goals
• 14: while game not terminated do
• 15: Receive current state St
• 16: Rule Matching:
• 17: for each rule Rulei in R do
• 18: Compute Pi(St)
• 19: end for
• 20: if any Pi(St) = 1 then
• 21: Select action πt = Actj for the first satisfied rule Rulej
• 22: else
• 23: Select action πt = {πh, if r ≤ 1 - pf rand, otherwise
• 24: end if
• 25: The chosen strategy interacts with the environment
• 26: end while
• 27: Rule Update:
• 28: if |∆sr| > δupdate then
• 29: Rextracted = ExtractRules(S)
• 30: R←Rextracted
• 31: Rabs = AbstractRules(R,Am)
• 32: Store Rabs for future rule grounding
• 33: end if
• 34: end for

3.2 Rule Matching and Reasoning

The rule matching and reasoning plays a pivotal role in HRLID, as it involves utilizing the rule set to guide the decisionmaking process. Before passing the policy from the upper layer to the lower layer, the policy undergoes evaluation using the rule set.

For each rule i in the rule set R, we evaluate the satisfaction of the rule's preconditions. Let Pi represent the set of preconditions for rule i. The evaluation of preconditions can be expressed as:

Here, Pi(St) is a function that assesses the preconditions Pi based on the symbolic representation St, and {0, 1} indicates whether the preconditions are satisfied (1) or not (0) for rule i at time t. If there exists a rule j in R whose preconditions are satisfied (i.e., Pj(St) = 1), we execute the policy induction suggested by rule j. Let Aj represent the action suggested by rule j. The rule application can be represented as:

Here, πt denotes the policy or action to be executed at time t. When the current state does not meet the prerequisites of any rule, the High-Level strategy comes into play. In the absence of applicable rules (i.e., if all Pi(St) = 0), we execute the original high-level strategy πh with a certain probability 1 - pf . This probability reflects the likelihood of executing a high-level strategy, enabling the model to balance exploration and exploitation during the learning process. This process can be expressed as:

Here, rand signifies random exploration, and pf is a probability value between 0 and 1. Each underlying reinforcement learning strategy has a probability value for random exploration, which gradually decreases as the number of choices increases.

The rule matching and reasoning process ensures that the model leverages rule-based strategies and logical decisionmaking, enhancing interpretability while preserving the hierarchical nature of the reinforcement learning framework. By combining rule-based decisions with the original high-level strategy, the HRL-ID framework achieves a more adaptive and efficient decision-making process.

3.3 Knowledge Generalization and Grounding

Knowledge generalization and grounding enables the model to repurpose the extracted knowledge for different domains. This intricate process entails the adaptation of these rules to align with the idiosyncrasies of the new environment, thus augmenting the model's adaptability and efficiency. Upon the extraction of a rule from a specific game environment, direct integration into the current environment is possible without necessitating any alterations. However, when the model seeks to employ rules from a distinct game environment within a new setting, adjustments become imperative. This process of adaptation is referred to as rule transfer. The model abstracts the rules extracted in a certain environment to a higher dimension, transforming them into more generic concepts. For example, the model might abstract the Key in the rules related to key collection in Montezuma's Revenge as the more abstract concept Collection, representing items that need to be collected. The rule abstraction process can be defined as:

where AbstractRules is a function that generates an abstract rule set Rabs based on the original rule set R and the mapping set Am, which stores the mapping relationships. This abstract rule set is designed to be universally applicable across different environments.

In the context of invoking these abstract rules within a fresh environment, the model scrutinizes the presence of input rules from disparate game environments. In the event of

• (b) Kangaroo
• (c) Adventure
• (a) Result of Montezuma's Revenge
• (c) Result of Adventure

Figure 3: Performance comparison on learning efficiency

such rules existing, the model undertakes a reverse abstraction to yield finely tuned rules germane to the new environment. Within a novel Kangaroo game environment, the model might correspondingly associate the concept of a Collection with an Apple, as the apple functions as a collection item within that contextual backdrop. The knowledge grounding and abstraction process empowers the model to harness its accrued reservoir of knowledge, adeptly generalizing across diverse game environments. By harmonizing the rules with the unique traits of the new environment, the model amplifies its efficacy in the learning process and subsequently, its overall performance. It's crucial to emphasize that the selection of rules for abstracting subgoals demands meticulous deliberation. This facet warrants further investigation in subsequent research endeavors. Our present methodology centers around the abstraction of the Collection element, considering it to be most conducive to generalization across disparate game environments. Nevertheless, the approach employed in our model presents a promising pathway for potential enhancements in the future.

4 Experiment

We evaluate our approach by applying it to the games Montezuma's Revenge, Kangaroo, and Adventure [Mnih et al., 2015]. The evaluation focuses on the average reward of the model in the scene and its generalization ability to other scenes. We commence our evaluation by focusing on Montezuma's Revenge, a quintessential Atari game characterized by intricate levels and multifaceted challenges. In this game, the agent undertakes a sequence of actions to secure rewards, which are notably sparse. This environment often poses a significant challenge for traditional algorithms like DQN, which frequently yield mere 0-point outcomes [Mnih et al., 2015]. Our experimentation begins with the selection of the game's initial setting, wherein tasks are meticulously designed to explore the agent's performance. As depicted in Figure 2(a), we frame the task as the agent's quest to acquire a key from the starting point and successfully return with it. The reward of +100 is designated for the accomplishment of obtaining the key. Subsequently, we extend our evaluation to the Kangaroo game (depicted in Figure 2(b)), an Atari game akin to Montezuma's Revenge. In this game, the agent confronts the challenge of evading enemy attacks while ascending to higher levels. In contrast toMontezuma's Revenge, the Kangaroo game features a more frequent reward distribution. The agent's task is to collect three specific items within the environment, each of which provides a reward of +100 points. We also evaluated our model in the Adventure game (illustrated in Figure 2(c)). In this Atari game, the objective is for the agent to gather certain items and proceed through multiple levels. Specifically, in the Adventure game, the condition for entering the next level is that the agent needs to find the key and open the door. The agent earns +100 points for acquiring the key and +300 points for unlocking the door, which in turn enables progress to the subsequent level.

(a) New game scenes

(b) New game scenes

ters on the average reward garnered by the agent during the game. Specifically, the agent's proficiency in key acquisition is treated as the primary assessment parameter. A higher evaluation reward, given the same number of steps, signifies swifter learning.

Within the initial Montezuma's Revenge environment, the outcomes of our experiments are depicted in Figure 3(a). Evidently, the introduction of extracted rules notably enhances training efficiency in terms of average reward. During the initial exploratory phase (first 0.2 million steps), all methodologies exhibit near-zero rewards due to ongoing environmental exploration. Nevertheless, as the step count surpasses 0.2 million, our approach surpasses NSRL methodologies and hierarchical reinforcement learning methods like HDQN in effectively uncovering rewards. This superiority stems from the guidance provided by previously extracted rules, steering the model toward optimal decision-making. In contrast, conventional methods such as DQN and A2C exhibit minimal advancement due to the inherent challenge of sparse rewards in orchestrating a series of decision-driven actions. Moreover, rule-based techniques offer streamlined training processes, as models assimilate knowledge from the extracted rules, culmi-

4.1 Experiment Setup

A variety of models were selected as the baseline model in the experiment, including traditional algorithms such as DQN and A2C [Keng and Graesser, 2017]. Furthermore, we introduce NSRL as a baseline, leveraging the identical parameter configurations as the original NSRL implementation [Ma et al., 2021]. We also incorporate hierarchical reinforcement learning HDQNmodels [Kulkarni et al., 2016] into the comparative spectrum. Pertaining to specific parameter settings, exploration phases are halted upon exceeding 500 steps within each round. The training reward function is structured as follows: the agent receives a certain negative reward (e.g. - 0.1) at each time step, and receives +10 points for completing a specified goal (e.g. reaching a subgoal). Conversely, losing a life or failing the game results in a penalty of -5. Furthermore, the meta-controller is assigned a penalty of -0.5 after each decision. At the base level, the DDQN algorithm [van Hasselt et al., 2016] is employed.

4.2 Comparison with SOTA Baselines

Our evaluation involves an assortment of approaches that serve as baselines. The key criterion for comparison cennating in superior performance within the same time frame.

The results of our experiments in the Kangaroo environment are presented in Figure 3(b). From the figure, it is evident that our approach outperforms the baseline models HDQN and NSRL right from the start of the training phase. This initial superiority can be attributed to our method's adept utilization of rules, furnishing early-stage guidance and direction for the agent's learning trajectory. While DQN and A2C initially exhibit better performance, this is likely due to our method's emphasis on item collection, eschewing other exploratory actions such as attacking enemies. The acquisition of items necessitates gradual learning in subsequent exploration phases. The learning curves elucidate that both our model and the NSRL model experience swift advancement, commencing around 200,000 steps. However, our method's curve ascension is more pronounced due to the rule-based approach employed in item collection. Explicit rules empower the agent to grasp the significance of collecting items, enabling enhanced environmental navigation and commensurately higher rewards. In contrast, the performance enhancement of the HDQN method is comparatively gradual. DQN and A2C are caught in a period of volatility. In addition, we use HDQN and NSRL as benchmarks to evaluate the effectiveness of our method in the Adventure game. Although Our method and the baseline have similar training curves, but ours performs better in the early stages.

4.3 Knowledge Transferability

In addition to leveraging rules during rule generation to enhance model training, we also develop rule transfer algorithms. This algorithm makes the rules extracted from one game environment applicable to other game environments to a certain extent, thus facilitating cross-environment learning. In this section, we extract the rules from the initial game environment of Montezuma's Revenge and transfer some of them to another game environment of the Montezuma's Revenge game (Figure 4(a)) and the kangaroo game (Figure 4(b)). For another game environment of Montezuma's Revenge, this is a simpler game environment, we want the agent to get the key and go to the bottom ladder, the reward of the key is also +100. We then evaluate the effectiveness of these transfer rules in these two environments. Finally, we extracted some of the rules in Montezuma's Revenge and Kangaroo during the experiment and presented them in Table 1 to illustrate the interpretability of the model. We compare with NSRL as the baseline. For the rule migration process, we prioritize the rules that are most likely to be effective, paying special attention to those that lead to direct score acquisition. For example, we extracted rules related to obtaining keys in the game Montezuma's Revenge, which may also work in other similar environments. Applying a rule transfer algorithm, we adapt these high-level abstract rules to new game environments.

Figures 4(c) and Figure 4(d) show the results of the experiments. We examine the training curves for the transferred rules in the middle section of Montezuma's Revenge and the Kangaroo game. Initially, the training curves are nearly identical, suggesting that our model has not yet fully identified the potential value of the transferred rules. However, as the training progresses, the curves begin to diverge, and the rules of migration start to come into play, particularly when items need to be collected. In the case of the middle part of Montezuma's Revenge game, the transferred rules show a positive impact on the agent's performance. These transferred rules provide valuable guidance, leading to more effective decision-making in collecting items within the new environment. Similarly, in the kangaroo game, the transferred rules also demonstrate a degree of effectiveness, aiding the agent in achieving its objectives more efficiently.

5 Conclusion

We propose HRL-ID, a neural-symbolic method that leverages automated knowledge discovery and reasoning for interpretable deep reinforcement learning. The proposal harnesses the potential of symbolic knowledge discovery and incorporating the discovered knowledge into the DRL framework for training acceleration. The knowledge abstraction and grounding in HRL-ID enables the agent to transfer existing knowledge and experience into new domains. The experimental results shows that HRL-ID outperforms SOTA baselines and successfully improves the learning efficiency and interpretability of DRL models. By providing transparent rule-based decision traces, HRL-ID bridges the gap between opaque DRL models and human-understandable reasoning, offering a robust solution for interpretable and efficient reinforcement learning.

Acknowledgments

The research of Haodi Zhang is supported by the Guangdong Provincial Key Lab of Integrated Communication, Sensing and Computation for Ubiquitous Internet of Things (No.2023B1212010007). Yuanfeng Song and Fangzhen Lin are the corresponding authors.