Authors:
(1) Kinjal Basu, IBM Research;
(2) Keerthiram Murugesan, IBM Research;
(3) Subhajit Chaudhury, IBM Research;
(4) Murray Campbell, IBM Research;
(5) Kartik Talamadupula, Symbl.ai;
(6) Tim Klinger, IBM Research.
Table of Links
Abstract and 1 Introduction
2 Background
3 Symbolic Policy Learner
3.1 Learning Symbolic Policy using ILP
3.2 Exception Learning
4 Rule Generalization
4.1 Dynamic Rule Generalization
5 Experiments and Results
5.1 Dataset
5.2 Experiments
5.3 Results
6 Related Work
7 Future Work and Conclusion, Limitations, Ethics Statement, and References
2 Background
Text-based Reinforcement Learning: TBGs provide a challenging environment where an agent can observe the current state of the game and act in the world using only the modality of text. The agent perceives the state of the game only through natural language observations. Hence, TBGs can be modeled as a Partially Observable Markov Decision Process (POMDP) (S, A, O, T , E, r), where S is the set of states of the game, A is the natural language action space, O is the set of textual observations describing the current state, T are the conditional transition probabilities from one state to another, E are the conditional observation probabilities, r : S × A → R is a scalar reward function, which maps a state-action pair to the reward received by the agent.
Inductive Logic Programming (ILP): ILP is a machine learning technique where the learned model is in the form of logic programming rules (Horn Clauses) that are comprehensible to humans. It allows the background knowledge to be incrementally extended without requiring the entire model to be re-learned. Additionally, the comprehensibility of symbolic rules makes it easier for users to understand and verify induced models and even edit them. Details can be found in the work of Muggleton and De Raedt (1994).
Answer Set Programming (ASP): An answer set program is a collection of rules of the form:
s(CASP) Engine: For this work, we have used s(CASP) ASP solver to predict an action. s(CASP) (Arias et al., 2018) is a query-driven, goal-directed implementation of ASP that includes constraint solving over reals. Goal-directed execution of s(CASP) is indispensable for automating commonsense reasoning, as traditional grounding and SATsolver based implementations of ASP may not be scalable. There are three major advantages of using the s(CASP) system: (i) s(CASP) does not ground the program, which makes our framework scalable, (ii) it only explores the parts of the knowledge base that are needed to answer a query, and (iii) it provides natural language justification (proof tree) for an answer (Arias et al., 2020).
3 Symbolic Policy Learner
Deep reinforcement learning (DRL) has experienced great success by learning directly from high-dimensional sensory inputs, yet it suffers from a lack of interpretability. Interpretability of an agent’s action is of utmost importance in sequential decision-making problems, as it increases the transparency of black-box-style agents; it also helps RL researchers understand the high-level behavior of the system better. To make a system interpretable, one of the most widely used approaches is learning the agent’s policies symbolically. In our work, EXPLORER learns these symbolic policies in the form of logical rules represented in the ASP. An example of such a rule is – insert(X, fridge) :- apple(X) which can be translated as “X is insertable into a fridge if X is an apple” [2]. These learned ASP rules not only provide a better understanding of the system’s functionality but can also be used to predict the agent’s next action using an ASP solver. EXPLORER learns the rules iteratively (in an online manner) and applies the rules to predict an action in collaboration with the neural module. Our results show that this approach is very effective in terms of performance and interpretability.
Partial Observability and Non-Monotonic Reasoning: EXPLORER works in a partially observable environment, where it needs to predict an action based on its prior knowledge. If EXPLORER fails, then it learns something new that will be applied in the next episode. The reasoning approach of EXPLORER is non-monotonic in nature: that is, what it believes currently may become false in the future with new evidence. We can model this using a non-monotonic logic programming paradigm that supports default rules and exception to defaults (Gelfond and Kahl, 2014). In this work, the belief of EXPLORER has been represented as an Answer Set Program in the form of default rules with exceptions. With the help of Inductive Logic Programming (ILP) (see Section 3.1) and Exception learner (see Section 3.2), these rules are learned by EXPLORER after each episode and then applied in the following episode. The agent uses an ASP solver to predict actions by utilizing the observation and the rules. Based on the outcome after applying the rules, the learned policies are updated with the exception (if needed), and new rules are learned as needed.
[2] For ease of use, we retain action names as the predicate names; however, they are interpreted normally as adjectives.
