Learning Two-Step Hybrid Policy for Graph-Based Interpretable Reinforcement Learning
Authors: Tongzhou Mu
Kaixiang Lin
Feiyang Niu
Govind Thattai
Venue: Accepted by TMLR ()

Abstract: We present a two-step hybrid reinforcement learning (RL) policy that is designed to generate interpretable and robust hierarchical policies on the RL problem with graph-based input. Unlike prior deep reinforcement learning policies parameterized by an end-to-end black-box graph neural network, our approach disentangles the decision-making process into two steps. The first step is a simplified classification problem that maps the graph input to an action group where all actions share a similar semantic meaning. The second step implements a sophisticated rule-miner that conducts explicit one-hop reasoning over the graph and identifies decisive edges in the graph input without the necessity of heavy domain knowledge. This two-step hybrid policy presents human-friendly interpretations and achieves better performance in terms of generalization and robustness. Extensive experimental studies on four levels of complex text-based games have demonstrated the superiority of the proposed method compared to the state-of-the-art. 

Published in Transactions on Machine Learning Research (10/2022)
Learning Two-Step Hybrid Policy for Graph-Based Inter- pretable Reinforcement Learning
Tongzhou Mu
t3mageng ucsd. edu
Deportment of Computer Science and Engineering University of California San Diego
Kaixiang Lin
kainiiam@@amazon.comm com
Amazon
Feiyang Niu
ofeityon Sjeezonnnommzoo.coom
Amazon
Govind Thattai
thatty Dartizanamazo..coo
Amazon
Reviewed on OpenReview:
https: openreview. net/ forum? id- 0m5
Abstract
We present two-step hybrid reinforcement learning (RL) policy that is designed to generate interpretable and robust hierarchical policies on the RL problem with graph-based input. Unlike prior deep reinforcement learning policies parameterized by an end-to-end black-box graph neural network, our approach disentangles the docision-making process into two steps. The first slep simplified classification problem that maps the graph input to an action group where all actions share a similar semantic meaning. The second step implements sophisticated rulc-miner that conducts explicit one-hop rcasoning over the graph and identifies decisive edges in the graph input without the necessity of heavy domain knowledge. This two-step hybrid policy presents human-friendly interpretations and achieves better performance in terms of generalization and robustness. Extensive experimental studies on four levels of complex text- games have demonstrated the superiority of the proposed method compared to the stale-of-the-art
1 Introduction
Recent years have witnessod the rapid developments of deep reinforcement learning across various domains such mastering board games Silver al. (2016); Schrittwieser el. al. (2020) playing video games Mnih et al. (2015). and chip design Mirhoseini et al. (2021), etc. The larger and complicated architecture of deep reinforcement learning models empowered the capabilities of resolving challenging tasks while brought in significant challenges of interpreting the decision making process of those complex policies Puiutta & Veith (2020). This trade-off between performance and interpretability becomes an inevitable issue when DRL is applied to high stakes applications such as health care Rudin (2019). In this work, we focus on basod interpretable reinforcement learning Zambaldi al. (2018); Waradpande al. (2020) as the
graph representation is expressive in various domains including drug discovery Patel
(2020). visual
question answering Hildebrandt et al. (2020). and embodied Chaplot et al. (2020); Huang al. 2019)
etc. Especially in robotics and embodied AI, the scene graph Zhou et al. (2019) of the environment is
general representation, which is widely used not only in building the environment
Puig et al. (2020): Kolve
et al. (2117) but also very effective when building the planning module Jia et al. (002): Min et al. (021
* Work done during internship Amazon Alexa AT.

---

Published in Transactions on Machine Learning Research (10/2022)
Another benefit of studying graph-based RL is that the graph structure can provide natural explanations
of the decision-making process without, the necessity of introducing new programs Verma et al. (2018) or
heavy domain knowledge Bastani et al. (2018) for interpretation. Prior works in interpretable reinforcement
learning Verma et al. (0118) Madumal et al. (2020); Liu et al. (2018) either works on restricted policy
class Liu et al. (2018) that leads to downgraded performance, or the interpretablility [Shu et al. (2017) 7
Zambaldi et al. (2018) limited. Another common issuc of interpretable RL is that the provided explanation
is generally difficult to comprehend for non-experts Du al. 2019))
In this work, we seek to obtain a human- aaaaaan-nddesttnndbbbl interpretation for the decision making process in graph-based tasks. To better illustrate the desired interpretability in graph-based tasks, we borrow the ideas from the visual recognition community, where people interpret how CNN works by analyzing which region gets the most attention, like Zhou et al. (2016): Zhang et al. 2018). Similarly, in graph-based tasks, we want to figure out the most crucial sub-graphs (or edges) used in decision making. We refer to this kind of interpretation as "interpretability" in graph- RL, not only because this kind of "interpretability" is similar to the one in the visual recognition community, but also because it is easily understood by humans. A crucial sub-graph also has several desirable characteristies of explanation defined by Molnar 2020) e.g., it is contrastive and selected.
To obtain the desired interpreability and resolve the challenges mentioned above, we propose a novel two-step hybrid decision-nie makiin process for general deep reinforcement learning methods with graph input. Our approach is inspired by the observation of human decision-making. When confront complicated tasks that involve expertise from multiple domains, we typically identify which domain of expert we would like consult first and then search for specific knowledge solutions to solve the problem. Recognizing the scope of the problem significantly reduces the search space of downstream tasks, which leads to more simplified problem compared to find the exact solution in all domains directly. As an analogy of this procedure, we disentangle a complicated deep reinforcement learning policy into a classification the problem for problem type selection and rule-miner. The classification establishes a mapping from complex graph input into an action type, which handles high-order logical interactions among node and edge represental ions with graph neural network. The rule miner conducts explicit one-hop reasoning over the graph and provides user- bree-friendly selective explanations Du et al. (2019) by mining several decisive edges. This two-step decision making is essential not only for providing interpretability, but also for generalization and robustness. It is intuitive to see that the simplified classification is easier to achieve better generalization and robustness than the original complicated RL policy. Furthermore, the rule-miner identifying key edges in the graph is much more robust to the noisy perturbations on the irrelevant graph components.
Our contributions can be summarized as below:
We propose general framework for two-step hybrid decision making, which is able to combine neural network and rule-based method together to make a decision while yielding human-friendly interpretations.
We instantiate our proposed framework in the setting of text-based games with graph input by proposing a novel rule miner for knowledge graphs.
Extensive experiments on several text- based games Côté et al. 2018) demonstrated that the proposed approach achieves a new state-of-the-art performance for both generalization and robustness.
2
Related Works
2.1
Interpretable RL
Instead of using deep RL as a black box, researchers also worked on making deep RL more interpretable. Mott et al.) 2019 Zambaldi et al. (2018) introduce some sorts of attention mechanism into policy networks
IThe idea of the crucial sub-graph also similar to the crucial point set used PointNe et graph neural network.
2017 which essentially
2

---

Published in Transactions on Machine Learning Research (10/2022)
and explain decision making process by analyzing attention weights. Verma al. (2018) combines program synthesis and PIDs in classic control to solve continuous control problems, while keep the decision making interpretable by explicitly writing the program. Combining symbolic planning and deep RL has similar effects, like Lyu et al. (201)). Tree-based policies Bastani et al. (2018) are favorable in interpretable RI, since they are more hemaaere and easy to verify. [Boneert et al. (2020) introduuces goal-based interprelability, where the agent produces goals which show the reason for its current actions. However, many existing works of interpretable RL sacrifices the performance for the interpretability. In contrast, our method achieves even better generalization and robustness while providing interpretability.
2.2 Hierarchical RL
Hierarchical RL focuses on decomposing a long- nog-horizon tasks into several sub-tasks, and applying a policy with hicrarchical structure to solve the task. Vezhnevets et al. (0177; Frans et al. (2018) try to solve generic long-horizon lasks with a two-level policy, where a high-level policy will generate a latent sub-goal for low-level policies, or directly select a low-level policy, and the low-level policy responsible for generating the final action. In some robot locomotion tasks, people usually manually define the choices of sub-goals boost the performance and lower the learning difficulty, like Nachum et al. (2018): Levy et al. (2018). In Multi-agent RL, hierarchical structure is commonly adopted policy structure to provide certain interpertability Gupta et al.. (2021); Mahajan et al. (2019); Wang et al.] (2020). However, those approaches can not explain how specific decision is associated with the stale space as their low-level policy is still a black box policy. Our two-step hybrid policy is reminiscent of the two-level policy architecture hierarchical RL. Unlike the high-level policy in hicrarchical RL mainly used to generate a sub-goal, the action pruner in our hybrid policy is also used to reduce the number of action candidates. And the motivations of our method and hierarchical RL also different: hierarchical RL targets decomposing a horizon tasks into several pieces, but our method focuses interpertability, generalizability and robustness.
2.3 Refactoring Policy
Given a trained neural nelwork-based policies, one may want to refactor the policy into another architecture, so as to improve the generalizibility or interpretablity. And this refactoring process is usually done by imitation learning. The desired architectures of the new policy can be decision tree Bastani et al. (2018). ) symbolic policy Landajuela et al. (2021), a mixture of program and neural networks [Sun et al. (2018), a graph neural networks Mu et al. (0220), hierarchical policy Bonaert et al. (2020). In our method, we also use similar techniques to refactor reinforcement learning policy into two-step hybrid policy.
2.4 Combine Neural Networks with Basee Models
Neural networks and rule-based models excel at different aspects, and many works have explored how to bring them together, like Chiu et al. (997)); Goodman et al. (1900] : Ray & Chakrabarti 2020 : Okajima & Sadamasa (2019); Greenspan
al. (1992). There are various ways combine neural networks with
rule-based models. For example, Wang [2019) combines them in a "horizontal' way, i.e., some of the data are assigned to rule-based models while the others are handled by neural networks. In contrast, work combines neural networks and rule-based models in a 'vertical' way, ie., the two models collaborate to make decisions in a two-step manner.
3 A General Framework for Two-Step Hybrid Decision Making
In this section, we first describe our problem setting including key assumptions and a general framework that formulates the decision-making process in two-step manner.
We consider a discrete time Markov Decision Process (MDP) with discrete state space S and the action space A is finite. The environment dynamics is denoted as P ip(s'|s,,0) a), Vs, E S,a A}. Given an action set A and the current state 8, E S, our goal is to learn a policy (T) that select an action at A to maximize the long-term reward E - a()] Assume we are able to group the actions into
3

---

Published in Transactions on Machine Learning Research (10/2022)
several mutual exclusive action types (At) according to its semantic meanings. More concretely, the k-th action type As- {ak ...., ) denotes subset of actions in original action space A₁ S A. Then we have A1, A,, A, A, n = 0(i + 5), U = A. It is worth noting that the number of action type K is usually much smaller than original actions (K < IA).
Let the policy क = Ss) represented by a hybrid model that consists of action pruner fp and action selector far The action pruner used to prune all available action candidates to a single action type, i.e, fp(s.) k, where & is the index of chosen action type and Ag {2, Ax]. Then the action sclector is used to select specific action given the action type chosen by the action pruner, ie., fa(s;, dss where a E As and k- = fp().).
Intuitively, this design intends to disentangle different phases in decision-making process to two different modules. On the one hand, determining the action type typically involves high-order relationships and needs a model with strong expressive power, then neural network is good candidate in this regard. On the other hand, selecting an action within a specific action type can resort to rule-based approaches, which is essential in providing strong intrepretability, generalizability and robustness.
Figure [ shows the overall pipeline of our two-step hybrid decision making. The agent will receive a state at each time step i. At time step i, we will first call the action pruner fp(s;) to select the action type A&. Then the rule-based action selector fa(8;, Ak,) will take as inputs the current state 8 and the action type As, given by action pruner to select the specific action to be executed in this step.
NN-based
Rule-based Action Selector
State
Action Type
Action
Action Pruner
Figure 1: Overall pipeline of the two-step hybrid decision making.
4 Swo-Step Hybrid Policy for Text-Based Games with Graph Input
4.1 Overview
In this section, we first discuss our considerations for investigating the interpretability of graph-based tasks and the reasons for using text-based games as our testbed. Firstly, graph is a powerful data structure, and it has been widely adopted in many real-world applications such as drug discovery Patel el al. (2020), visual question answering Hildebrandt et al. (2020), and embodied AI [Chaplot et al. (2020); Huang al. (2019), etc. Mcanwhile, the discrete nature and the explicit semantic meaning of graphs (c.g., the relationship of related nodes) provide an easily understandable format for elaborating the decision-making process even for a non-expert. However, the interpretability of graph-based RT. tasks is still rarely explored. On the other hand, it is challenging to provide interpretability without any assumption on the action space, even for graph-baser RL. We focus on tasks with hierarchical/ hicrarehial/compootionn ccomosstiinnll action spaces as a starting point,
which a common setting embodied AT. Considering the text- scene graph has been a general representation of embodicd AI tasks Shridhar et al., (2020), we instantiate our proposed framework in the setting of text-based games Côté et al. (2018) with graph input. In text-based games, the agent receives a knowledge graph (as shown in Figure 3 that describes the current state of the environment and the task to be completed, c.g., the task can be represented by several edges like ("potato', "needs', "diced'). Our goal is to learn a policy that maps the input knowledge graph to an action from the provided action set A. Each action aj E A is a short sentence, e.g., "take apple from fridge'.
In this setting, we use graph neural networks (GNNs) as the action pruner fpr and a rulc-basod model as the action selector fa. We will elaborate the details of the action pruner and the action selector in See 4.4 and Sec 4.5 respectively. A brief description of GNNs can be found in See 4.2
4

---

Published in Transactions on Machine Learning Research (10/2022)
Training the GNN-based action pruner and the rule-based action selector by reinforcement learning is nontrivial since the whole pipeline is not end-to-end differentiable. Therefore, propose to learn both models separately from demonstration dataset, and the demonstration dataset can be obtained by a trained reinforcement learning agent. We will claborate the details in Sec 4.3.1 This process inspired by existing works like Bastani et al. (2018); Landajuela et al. (2021;: Sun et al. (2018) Mu el al. (2020), where policies trained by reinforcement learning can be refactorized into other forms.
4.2 Backgrounds on Graph Neural Networks
We briefly describe commonly used class of GNNs that encompasses many state-of-art networks, including GCN Kipf& & Welling (2016), GAT Veličković et al. (2017). GIN Xu al. (2018), etc. The class of GNNs generalizes the message- pastggnggg framework Gilmer et al. (2017) to handle edge attributes. Each layer of it can be written as
h = fh fze: e Ne(v)), (hi o' E (v)
where hy is the node feature vector of node v at layer l. (v) and NEE()) denote the sets of nodes and odges that are directly connected to node (i.e. its 1-hop neighborhood). fo parameterized function, which is usually composed of several MLP modules and aggregation functions (e.g. sum/max) in practice.
4.3 Preparing Datasets for Learning Two-Step Hybrid Policy
4.3.1
Demonstration Acquisition
Given a set of interactive training environments, the goal of this step is to obtain a demonstration dataset, which contains state-action pairs from a policy achieving high reward in the training environment. Specifically, we aim al generating a demonstration dataset D = ((*,, π (s+))) where 8; is the input state (a knowledge graph in our cases) from the training environments, and (s:)) is the output of demonstration policy on the state 8;- The representation of =(s;) is flexible: it can be an action, the logits, any latent reprosentation, which indicates the demonstration action distribution. This dalaset will be used for learning our two-step hybrid policy.
We refer the policy used to generate demonstration as teacher policy. It can be obtained in any way, as long as it provides reasonable and good supervision on how to solve the task in the training environments, and it is not necessary to have strong interpretablity, generaliziabilty or robustness. Therefore, deep reinforcement learning is great tool to learn such a policy.
After obtaining the teacher policy, we use it to interact with the training environments to collect states and label them with the output of the teacher policy. During the interaction, we add action noise to the state distribution in the demonstration dataset. A more diversified state distribution is beneficial to the performance of our two-step hybrid approach.
perturb
4.3.2 Action Grouping and Demonstration Splits
As mentioned above, the action pruner is responsible for selecting the correct type of actions for the current state, so that the action candidates will be pruned to a smaller set. Then, a rule-based model will work on this specific action type to select the action to be executed. Therefore, we need to label each state with the action type. Since the action for cach state already in the dataset, we just ncod convert each action into an action lype. In other words, we need to group all possible actions into several action types.
In bastd games, each action is short sentence with semantic meaning, e.g., "take apple from fridge", Intuitively, we can group the actions by their semantic mcaning. For example, if the actions are "take apple from fridge", "slice polato with knife', "dice cheese with knife', "cook carrot with oven', and "cook onion with stove', we can group them into three types: "take" actions, "cut" actions, and "cook" actions. And we make sure all the actions with the same action type follow the same template, e.g., the template of "take' action can be written as "take object from receptacle", where object and receptacle can be instantiated by appropriate words.
5

---

Published in Transactions on Machine Learning Research (10/2022)
Grouping actions by semantic meanings also aligns with our motivation: 1) After obtained K group of actions, we substantially alleviate the workload of neural networks from learning a policy that maps states to an action in a varying size and high-dimensional action space to a simplified classification with a much smaller number of classification categories. This simplification could greatly reduces the sample-complexity 2) Furthermore, this step also creates a much smaller search space enable the rule-miner to search within a feasible candidates set.
Formally, given dataset D= {(s;, ((s)))) we will generate action type for each state, policy output (st, (s.)) pair. The action type Kę is determined by k = h(((s;)), where (s)(s:)) is a domain-specific function which takes the semantic meaning of the action into consideration. As result of the clustcring process, we will get a new demonstration dataset with action types D = (s;),, ki) In addition, we can also split the demonstration dataset based on the action types to get K subset of the original demonstration dataset, (D1, .... D where D (s, x (8()))(((()))) k).
4.4 GNN-based Action Pruner
The action pruner needs to output an action type based the imput knowledge graph, so it is essentially classifier. Given the demonstration dataset D = {[s;, k obtained in the last step, want to train a classifier (s = k, where & E 21,2,..., K} is an action type. This is a conventional classification problem which can be solved by minimizing cross entropy loss:
K ΣΣ
0 = arg min-
kg (o)))
where fs()s) outputs probability distribution over the K action types, fa (s:) denotes the j-th action type's probability. 2 E [0,1) 1} denotes denotes whether the action type j was chosen in the demonstration dataset. at state
4.5 Rule Based Action Selector
4.5.1 Abstract Supporting Edge Sets
When the input is a knowledge graph, the action is naturally strongly correlated with some critical edges. For example, ("potato', "needs', "diced') and ("potato", "in", "player') can lead to the action "dice potato". We refer those decisive edges correlating to an action as the supporting edge set of this action. Since we have grouped actions by their semantic meanings, actions within each action type are actually supported by similar edges. For example, "dice potato' is supported by ("potato', "in', "player"), and "dice apple" is supported by ("apple', "in", "player"). As mentioned in See 4.3.2 each action type comes with action template like "dice object'. Based on the action template, an input knowledge graph labeled with action "dice apple", we can replace all the "apple" appearing in the graph edges and the action with an abstract name "object'. Then we can say the action "dice object' is essentially supported by ("object', "in', "player"), where the two "object" should be instantiated by the same word. Under this kind of abstraction, different actions within the same action type can share same abstract supporting edge set which contains edges with abstract names.
can perform some sorts of abstraction. For example, given
The abstract supporting edge set indicates the decisive edges for action type, and it can be instantiated for each specific action. For example, to check whether the action *dice apple' should be executed, the abstract edge ("object', "in', "player") will be instantiated to edge ("apple", "in', "player"). Then, the existence of ("apple", "in", "player") in input knowledge graph becomes an evidence for selecting the action "dice apple". We aim at finding an abstract supporting edge set for each action type, and it will be used during inference.
4.5.2 Mine Abstract Supporting Edge Sets from Demonstrations
Finding the abstract supporting edge set for each action type is actually a rule mining process. There are several off-the-shelf rule miners like FP-Growth Han et. al. (2004). Apriori Agrawal et al. (1994). Eclat Zaki
6

---

Published in Transactions on Machine Learning Research (10/2022)
Action Type
Abstract Supporting Edge Set
Action
cook
[object, needs, cooking method] [object, in, player]
cook potato with oven
Action Pruner
Supporting Edge Set
Input Knowledge Graph
Action Score
[potato, needs, roasted] [potato, in, player]
[player, at, kitchen] [potato, needs, roasted] [fridge, is, open] [potato, in, player]
2
An example of using supporting edge set to score an action. Based on the knowledge graph, the action pruner first predict the action type (e.g., cook) that needs to be taken at current state, then instantiate the abstract supporting edge set to concrete supporting edge set. Comparing the input knowledge graph with the supporting edge set, we can compute action score for each action and select the action with highest score accordingly.
Figure 2:
2000), etc. but they are not designed for knowledge graphs. Thus, we propose simple yet effective rule miner for our setting discover the supporting edge sets.
To find the Abstract Supporting Edge set ASE(AA) for each action type Ag, designed numerical statistic that is intended to reflect the importance of edge when taking action A, and this numerical statistic is inspired by tf-idf RRaaaraaan & Ullman (2011). Formally, for action type Ag, we have a corresponding subset of demonstration dataset Dr = {s:} (ignoring n; here) where all the actions are within the action type Ag. Under the abstraction mentioned above, we can count the edge frequency for every (abstract) edge in D;:
[s,ss,, DR. s:Hl
frequ(e)
[Dx
Similarly, we can also count the edge frequency for the entire demonstration dataset:
frea(e) Hs E
[D]
And can define importance score of edge w.r.t to the action type Ag:
Te(e) = frequ(e) log( freg(e) )
where the term frequ(e) is similar to the term-frequency (tf), and the term log( f is similar to the inverse document frequency (idf).
Then we can get the ASE(As) by selecting the edges with the importance higher than threshold, iec. ASF(As) (e) > T}, where is hyperparameter shared across all action types.
7

---

Published in Transactions on Machine Learning Research (10/2022)
4.5.3 Inference Based on Supporting Edges
During inference, we use the supporting edge sets to score each action within the action type provided by action pruner, and select the action with the highest score. Figure shows concrete example of using supporting edge set to score an action.
Firstly, the action priner outputs action type based the imput knowledge graph, and can retrieve the abstract supporting edge set of this action type. Secondly, given action within the action type, can instantiate the abstract supporting edge set to a specific supporting edge set by replacing the abstract names by the concrete words according to the action, c.g, ("object", "in", "player") will be instantiated to ("potato', "in", "player") the action "cook polato with oven'. Finally, we can compare the input knowledge graph with the supporting edge set of each action to figure out which supporting edge set is best covered by the input knowledge graph. The number of overlapped edges between the supporting edge set and the the input knowledge graph will be regarded the score of the action.
Formally, the inference process of our rule-based action selector can be described as follows
[a(8, A) = arg max |s n SE(a)),
aEA
where SE(a) is the supporting edge set associated with action a, which is obtained by instantiating the abstract supporting edge set of action type A.
5
Experiments
5.1
Dataset Setup
Difficulty Level
Recipe Size
Number of Locations
Need
Need Cook
Number of Action Candidates
Number of
Number of Sub-tasks
Cut
Objects
1
1
Yes
No
11.5
17.1
4
1
Yes
Yes
11.8
17.5
5
3
1
9
No
No
7.2
34.1
3
4 3
6
Yes
Yes
28.4
33.4
11
Table 1: World games statistics (averaged across all gamns within a difficulty level). The games and statistics are generated by Adhikari et al. (2020).
We evaluate our method on World, which is a framework for designing text-based interactive games. More specifically, we use the Text games generated by GATA Adhikari et al. (2020). In these games, the agent asked to cook a meal according to given recipes. requires the agent to navigate among different. rooms locate and collect food ingredients specified in the recipe, process the food ingredients appropriately, and finally cook and cat meal.
The state received by the agent is a knowledge graph describing all the necessary information about the game. All the nodes and edges in the knowledge graph are represented in text. Figure 3 shows a partial example of input knowledge graph. The actions are also represented in text. Note that the number of available actions vary from state state, so most of of existing network architecture used deep reinforcement learning cannot. be directly used here.
The games have four different difficulty levels, and each difficulty level contains 20 training, 20 validation, and 20 test environments, which sampled from a distribution based the difficulty level. The higher the difficulty levels are, the more complicated recipe will be and the more rooms food ingredients will be distributed among. For easier games, the recipe might only require single ingredient, and the world is limited to a single location, whereas harder games might require an agent to navigate a map six locations collect and appropriately process up three ingredients. Statistics of the games are shown Table [ For evaluating model generalizability, we select the top-performing agent on validation sets and report its test scores; all validation and test games unseen in the training set.
8

---

Published in Transactions on Machine Learning Research (10/2022)
5.2
Implementation Details
uncut
fried
diced
5.2.1 Process Knowledge Graphs by GNNs
needs
needs
is
is
raw
Graph neural networks (GNNs) serve as backbone networks in both our RL teacher policy and the action priner in our two-step hybrid policy. More specifically, we use the Relational-GCN to take edge attributes into consideration, and the Relational-GCN also the backbone architecture used in GATA Adhikari et al. (2020), which is the baseline method in the World games used. Actually, the choice of the network architecture is not very important in our method. This is because both the RL teacher policy and the action pruner are only used to fit the training environments or the demonstration dataset. We did not really expect them to have strong interpretability, because this the job of the rule- based action selector. Therefore, most graph-based networks with sufficient capacity should be good in cases. We will also perform ablation study about network architecture in Sec. 5.4
Orange bell
pepper
Yellow bell
pepper
part of
needs
in
Fridge
fried
Cookbook
is
needs
part_ of
closed
in
raw
The relations and nodes of the input knowledge graphs are initially represented in text. (words or short sentences). We use Text Mikolov et al. (2017), pre-trained on Common Crawl, to convert each token to an embodding, and then average all the token embeddings to oblain the mean fast/ext embedding of the entire text. string. These mean Text embeddings are pre-computed and fixed during training. For each relation and node, append their corresponding mean fast Text embedding with trainable embedding vector. The concatenated embeddings are then used as the numerical representation each relation and node. Finally, a graph with numerical reletrelaiion features is passod through GNNs to get the latent embedding of the entire input knowledge graph.
White
uncut
is onion
is
Figure 3: Visualization part of an input knowledge graph Text World.
5.2.2 Demonstration Acquisition
To collect demonstration datasct, we first train teacher policy by DQN Mnih al. (2015) in the training environments, which can converge to a near-optimal solution. To adopt variable number of available actions, we let the policy network take the state and an available action as input and output a score for this action. And we can select the action with maximum score as the final output.
The trained leacher policy is used to collect 300K samples through the interaction with the environment, and label them with the taken actions, as illustrated in Sec [.3.1] When collecting the demonstration dataset, we use e-greedy exploration strategy to increase the diversity of states.
5.3 Results
5.3.1 Interpretability
The interpretablity of our two-step policy is Iwo-fold: 1) the transparent (wo-step decision making process; 2) the rule-based models make decisions in way which is easy to interpret by human.
Table shows some representative rules discovered by our rule miners. We observed that all of the four discovered abstract supporting edges are indeed prerequisites of the "cut." actions. In particular, the abstract supporting edge ("object', "needs', (verb_paasivee)) is a crucial prerequisite for the agent to select the correct verb in the "cut" actions. For example, if the input knowledge graph contains the edge ("potato", "noods', "sliced"), then the action "slice potato with knife" will get one more score than others because this edge is in the supporting edge set of action "slice potato with knife'.
9

---

Published in Transactions on Machine Learning Research (10/2022)
Action Type: Cut
Example Action
Action
verb object with knife
slice potato with knife
Head
Relation
Tail
Importance
Head
Relation
Tail
object object
in needs part of is
player
1.7004
polato
in needs sliced part of cookbook uncut.
player
Discovered
verb passive
1.6659
potato
Supporting
object
cookbook
1.0058
polato
Edges
object
uncut.
0.9837
potato
Table 2: Discovered abstract supporting edges of the "cut" action type in difficulty level 1 of Text World environments. The importance of each edge is computed by the metric mentioned in Sec 4.5.2 The right column gives an example action and the corresponding supporting edge set, which is obtained by instantiating the abstract supporting edge set. The underlined words are abstract names for some cerlain words. For example, "verb" in action can be instantiated to "slice', "dice" or "chop', and "verb passive_ can instantiated to "sliced'; "diced' or "chopped" accordingly.
Since we clearly see the rule-based model makes decisions based on these rules, it is not hard to check whether this model works a correct way. In this way, the agent can cortainly select the correct "cut" action even unseen Lest environments.
5.3.2 Generalization
Training
Test
Difficulty
2
1
4
GATA-GTF
98.6
58.4
95.6
36.1
83.8
53
33.3
23.6
Vanilla RL
100
100
98.3
100
83.8
68
50
30.9
Ours
100
100
100
65.5
100
100
51.7
49.7
Table 3: Evaluation results on both training environments and test environment in Torld The numbers
show the agent's 's normalized scores.
We compare with two basclines: GATA-GTF and vanilla RL. GATA-GTF a variant from GATA Adhikari et al. (2020), and uses the same ground-truth graph imput as us. GATA-GTF processes the input graphs by relational graph convolutional networks (R-GCNs) Schlichtkrull al. (2118), and the whole pipeline is trained by DQN Mnih et al. (2015). Vanilla RL is essentially the same method with GATA-GTF, but implemented by ourselves. With better implementation and careful hyperparameter tuning, it performs better than the implementation released by the GATA authors. And vanilla RL also serves the teacher policy which used to generate demonstrations for our method.
Table g shows the normalized scores of different methods on both training environments and test environment Text World. The result GATA-GTF is obtained from its paper Adhikari et al.) (2020). Tn all the environments, our agent achieves better generalization performance the vanilla RL (which is our RL teacher) and GATA-GTF baselines. Our agent can generalize pretly well to the unseen test environments in all difficulty levels, while the performance of GATA-GTF and vanilla RL performs poorly in unseen test environments.
5.3.3 Robustness
As mentioned above, our method also aims al robustness. To evaluate the robustness of our models, we add different levels of noises to input knowledge graphs and regard the performance the agents under noisy inputs. In this paper, we define the noise on knowledge graph as adding additional edges to the graph or dropping existing edges in the graph. Formally, we add noise at (k, pe-ee input knowledge graph in the following way:
10

---

Published in Transactions on Machine Learning Research (10/2022)
Noise
Difficulty
2
3
Add
Drop
RL
Ours
RL
Ours
RL
Ours
RL
Ours
0.2
0
100(0%)
100(0%)
100(0%)
100(0%)
96(-1%)
98(-1%)
38(-61%)
64(-1%)
0.2
0.03
100(0%)
96(-3%)
81(-19%)
98(-1%)
80(-18%)
98(-1%)
41(-58%)
51(-21%)
0.2
0.06
100(0%)
92(-7%)
93(-6%)
82(-18%)
86(-11%)
93(-6%)
44(-55%)
41(-36%)
0.4
100(0%)
100(0%)
85(-15%)
100(0%)
65(-33%)
91(-8%)
19(-80%)
58(-11%)
0.4
0.03
100(0%)
100(0%)
77(-23%
90(-9%)
71(-27%)
91(-8%)
20(-79%)
53(-18%)
0.4
0.06
100(0%)
96(-3%)
78(-22%)
83(-16%)
65(-33%)
96(-3%)
19(-80%)
49(-24%)
0.6
100(0%)
100(0%)
85(-15%)
100(0%)
76(-22%)
93(-6%)
8(-91%)
59(-9%)
0.6
0.03
100(0%)
97(-2%)
75(-25%)
83(-16%)
61(37)%
86(-13%)
9(-90%)
39(-99%)
0.6
0.06
100(0%)
91(-8%)
76(-24%)
80(-20%)
60(-38%)
96(-3%)
10(-89%)
46(-29%)
Table 4: Robustness analysis of our method and vanilla RL baseline. We evaluate the performance of agents on training environments under different noise levels, e.g., "add 0.2 drop 0.03" means we randomly add 20% additional edges while randomly dropping 3% existing edges in graph. The numbers out of parentheses are normalized scores and the numbers in parentheses are relative performance change comparing to the performance without input noise. The bold numbers indicate which method performs better in cach sctting.
Add edges: [ * [E]] additional edges will be randomly generated and added to the graph, where E the edge set of the graph. For each edge bi, 4i head node h; and tail node are sampled from Vau and relation r; is sampled from Rail, where Vau means the set of all possible nodes and Rau is the set of all possible relations.
2. Drop edges: [p ['] edges will be dropped from the graph. Note that only original edges will be dropped, and the randomly added edges will not be dropped.
Table 4 shows the performance of vanilla. RL and method under noisy input graphs generated in the above mentioned way. Note that we test robustness in training environments instead of test environments, because the performance of both agents in test environmenls are not good enough and examining robustness of poor-performed agents does not make too much sense.
We observed that in difficulty level 1, both agents are very robust under the noisy inputs. However, in difficulty level 2 & 4, the performance of the RL agents are hurts a lot by the input noises, especially the difficulty level 4. In contrast, the agents obtained by our method are still performs pretty good and the performance drops significantly less than the RL agents.
5.4 Ablation Study
In this section, we study the contributions of different modules in our method. Our proposed method mainly consists of three modules: 1) an RL teacher policy, 2) GNN-based action pruner, 3) rule-based action selector. Therefore, we replace each module with other alternatives and see how the generalization performance is influenced. All the experiments below are performed on the TextWorld games with difficulty level 1.
5.4.1 RL teacher policy
We first study how different kinds of teacher policies affects the performance. We consider the following three alternatives to our RL teacher policy: 1) an RL teacher policy with different backbone network: Graph Transformer Network (GTN) Yun et al. (2019); 2) a manually written ground truth policy which can perfectly solves the tasks; 3) a random policy, Note that we choose ground truth policy and random policy as teachers because they represent two extreme cases: very good teacher and very bad teacher.
Table shows the results of this ablation study. From this table, we observe the following things:
11

---

Published in Transactions on Machine Learning Research (10/2022)
Method Variant
Training
Test
Ours (backbone is GCN)
100
100
Use GTN as backbone of teacher
100
100
Use ground truth policy as teacher
100
100
Use random policy as teacher
8.8
15.0
Table 5: Evaluation results on both training environments and test environment. in Text difficulty level 1. The numbers show the agent's normalized scores.
It does not. make much difference by switching the backbone of the RL Leacher policy from GCN to GTN. This verifies our expectation: any graph-based network should be good as long as it has sufficient capacity for the training environment data, because the job of the RL teacher is only to provide demonstration dataset.
Using ground truth policy also does not really affect the performance of our method. Since our RL teacher policy actually achieves almost perfect performance on the training environments, the demonstrations gencrated by our RL teacher and the ground truth policy are almost oqually good.
Using a random policy does not work at all. This also meets our expectation that a good demonstration dataset is very important for learning the action pruner and the rule-based action selector.
5.4.2 GNN-based action pruner
In this section, we mainly assess the influences the network architectures used the GNN-based action pruner. Specfically, we replace the backbone of our action pruner with Graph Transformer Network (GTN)
Yun et al. (0019) And we also study the case where the RL teacher also uses GTN as the backbone.
Method Variant
Training
Test
Ours (GCN teacher, GCN action pruner)
100
100
GCN teacher, GTN action pruner
100
100
GTN teacher, GTN action pruner
95
100
Table 6: Evaluation results on both training environments and test environment in ToxtWorld difficulty level 1. The numbers show the agent's normalized scores.
From the Table 6 can that the architecture changes have minimal influence the performance. This verifies our expectation again: any graph-based network should be good as long it has sulficient capacity for the training environment / data. Though the "GTN teacher, GTN action pruner" variant does not get full scores on the training environment, the performance gap is very small.
5.4.3 Rule-based action selector
Finally, we study whether a rule-based action selector crucial by replacing it with network-based action selector. The resulting policy is somehow like mixture of experts, where the gating function and the experts are all networks.
Method Variant
Training
Test
Ours (rule-based action selector)
100
100
GCN-based action selector
100
70
Table 7: Evaluation results both training environments and test environment. in World difficulty level 1. The numbers show the agent's normalized scores.
12

---

Published in Transactions on Machine Learning Research (10/2022)
that the network-based action selector does good job in the training environments but performs poorly on the test enviromments. This is because the network-based action selector overfits the training data instead of really learning the underlying rules of decision making. In contrast, our rule-based action selector learns the real underlying rules that generalize well. Therefore, the rule-based action selector a crucial component of our method.
From the Table 7
6 Conclusion
this work, we propose a two-step hybrid policy for graph-based reinforcement learning. The two-step hybrid policy discntangles complicated black-box deep reinforcement Icarning policy into an action pruncr and an action selector. The joint effort of two modules can not only generate each decision, but also provide significantly better performance in terms of generalization and robustness. We conduct comprehensive experiments on the representative text-based environments Côté et al. (2018) to demonstrate the effectiveness of our approach.
explanations of
13

---

Published in Transactions on Machine Learning Research (10/2022)
References
Ashutosh Adhikari, Xingdi Yuan, Mare-Alexandre Côté, Mikuláš Zelinka, Marc-Antoine Rondeau, Romain Laroche, Pascal Poupart, Jian Tang, Adam Trischler, and Will Hamilton. Learning dynamic belicf graphs to generalize on text-based games. Advances in Nearul Informalion Processing Systems, 33, 2020.
Rakesh Agrawal, Ramakrishnan Srikant, et al. Fast algorithms for mining association rules. In Proc. 20th ind. conf. very large data bases, VLDB, volume 1215, pp. 487-499. Citeseer, 1994.
Osbert Bastani, Yewen Pu, and Armando Solar-Lezama Verifiable reinforcement learning via policy extraction. Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 2499 2509, 2018.
Gregory Bonaert, Youri Coppens, Denis Steckelmacher, and Ann Nowe, Explainable reinforcement learning through goal-based interpretability. 2020.
Devendra Singh Chaplot, Ruslan Salakhutdinov, Abhinav Gupta, and Saurabh Gupta. Neural topological slam for visual navigation. In Proceedings of the IEEE/CVF Conference on Compuler Vision and Pallern Recognition, pp. 118844 2020.
Chih-Chou Chiu, Ling-Jing Kao, and Deborah F Cook. Combining a neural network with rule-based expert system approach for short-term power load forccasting in taiwan. Expert Systems with Applications, 13(4): 299 305, 1997.
Marc-Alexandre Côté, Akos Kádár, Xingdi Yuan, Ben Kybartas, Tavian Barnes, Emery Fine, James Moore, Matthew Hausknecht, Layla El Asri, Mahmoud Adada, al. Textworld: A learning environment for text-based games. In Workshop Computer Games, pp. 41-75. Springer, 2018.
Mengnan Du, Ninghao Liu, and Xia Hu. Techniques for interpretable machine learning. Communications of the ACM, 63(1))68 77, 2019.
Kevin Frans, Jonathan Ho, Xi Chen, Pieter Abbeel, and John Schulman. Meta. learning shared hierarchies. In International Conference on Learning Representations, 2018.
Justin Gilmer, Samuel S Schocnholz, Patrick F Riley, Oriol Vinyals, and George Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp. 1263 1272. PMLR, 2017.
Rodney M Goodman, Chuck Higgins, John Miller, and Padhraic Smyth. A rule-based approach to neural network classifiers. In International Newral Network Conference, pp. 886-889. Springer, 1990.
Hayit K Greenspan, Rodney Goodman, and Rama Chellappa. Combined neural network and rule-based framework for probabilistic pattern recognition and discovery. 1992.
Tarun Gupta, Anuj Mahajan, Bei Peng, Wendelin Böhmer, and Shimon Whiteson. Uneven: Universal value exploration for multi-agent reinforcement learning. In International Conference Machine Learning, pp. PMLR, 2021.
Jiawei Han, Jian Pei, Yiwen Yin, and Runying Mao. Mining frequent palterns without candidate generation: A fratuent-pattern tree approach. Data mining and knowledge discovery, 8(1):53 87, 2004.
Marcel Hildebrandt, Hang Li, Rajat Koner, Volker Tresp, and Stephan Günnemann. Scene graph reasoning for visual question answering. arxiv preprint arXiu:2007.01072, 2020.
De-An Huang, Suraj Nair, Danfei Xu, Yuke Zhu, Animesh Garg, Li Fei-Fei, Silvio Savarese, and Juan Carlos Niebles. Neural task graphs: Generalizing to unseen tasks from a single video demonstration. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 1565-8574- 2019.
Zhiwei Jia, Kaixiang Lin, Yizhou Zhao, Qiaozi Gao, Govind Thattai, and Gaurav Sukhatme. Learning to act with a afforrence multimodal neural slam. arXio preprint ar 201:22201.0966,, 2022.
14

---

Published in Transactions on Machine Learning Research (10/2022)
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. ar preprint Xiv: 029007 2016.
Eric Kolve, Roozbeh Mottaghi, Winson Han, Eli VanderBill, Luca Weihs, Alvaro Herrasti, Daniel Gordon, Yuke Zhu, Abhinav Gupta, and Ali Farhadi. Ai2-thor: An interactive 3d environment for visual ai. arXiv preprinl Xiv: (7tc.0512, 2017.
Mikel Landajuela, Brenden K Petersen, Sookyung Kim, Claudio P Santiago, Ruben Glatt, Nathan Mundhenk, Jacob F Pettit, and Daniel Faissol. Discovering symbolic policies with deep reinforcement learning. Tn International Conference on Machine Learning, pp. 5979 5989. PMLR, 2021.
Andrew Levy, George Konidaris, Robert Platt, and Kate Sacnko. Learning multi-level hicrarchics with hindsight. In International Conference on Learning Represenlalions, 2018.
Guiliang Liu, Oliver Schulte, Wang Zhu, and Qingcan Li. Toward interpretable deep reinforcement learning with linear model u-trees, In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 414-429. Springer, 2018.
Daoming Lyu, Fangkai Yang, Bo Liu, and Steven Gustafson. Sdrl: interpretable and data-efficient deep reinforcement learning leveraging symbolic planning, In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 2970-2977, 2019.
Prashan Madumal, Tim Miller, Liz Sonenberg, and Frank Vetere. Explainable reinforcement learning through a causal lens. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 2400, 2020.
Anuj Mahajan, Tabish Rashid, Mikayel Samvelyan, and Shimon Whiteson, Maven: Multi-agent variational exploration. Advances in Neural Information Processing Systems, 32, 2019.
Tomas Mikolov, Edouard Grave, Piotr Bojanowski, Christian Puhrsch, and Armand Joulin. Advances in pre-training distributed word representations. arXiv preprinl ar Xiv:::1122 09405, 2017.
So Yeon Min, Devendra Singh Chaplot, Pradeep Ravikumar, Yonatan Bisk, and Ruslan Salakhuldinov. Film: Following instructions in language with modular methods. arXiv preprint arxiv:21 100-0224, 2021.
Azalia Mirhoseini, Anna Goldie, Mustafa Yazgan, Joe Wenjie Jiang, Ebrahim Songhori, Shen Wang, Young- Joon Lee, Eric Johnson, Omkar Pathak, Azade Nazi, et al. graph placement methodology for fast chip design. Nalure, 204(7862)2007-22 222, 2021.
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):529 533, 2015.
Christoph Molnar. Interpretable machine learning. Lulu. com, 2020.
Alexander Mott, Daniel Zoran, Mike Chrzanowski, Daan Wienstra, and Danilo Jimenez Rezende. Towards interpretable reinforcement learning using attention augmented agents. In Advances in Neural Information Processing Systems, pp. 12329-1238 2019.
Tongzhou Mu, Jiayuan Gu, Zhiwei Jia, Hao Tang, and Hao Su. Refactoring policy for compositional generalizability using self-supervised object proposals. Advances in Neural Information Processing Systems, 33, 2020.
Ofir Nachum, Shixiang Shane Gu, Honglak Loe, and Sergey Levine. Data-efficient hicrarchical reinforcement learning. Advances in Neural Information Processing Systems, 31:3303 3313, 2018
Yuzuru Okajima and Kunihiko Sadamasa. Deep neural networks constrained by decision rules. In Proceedings of the AAAT Conference on Artificial Intelligence, volume 33, pp. 2496 2505, 2019.
15

---

Published in Transactions on Machine Learning Research (10/2022)
Lauv Patel, Tripti Shukla, Xiuzhen Huang, David W Ussery, and Shanzhi Wang. Machine learning methods in drug discovery. Molecules, 25(22):5277, 2020.
Xavier Puig, Tianmin Shu, Shuang Li, Zilin Wang, Yuan-Hong Liao, Joshua B Tenenbaum, Sanja Fidler, and Antonio Torralba. Watch-and-help: challenge for social perception and human-ai collaboration. arXiv preprinl ar 2000 09890, 2020.
Erika Puiutta and Eric MSP Veith. Explainable reinforcement learning: A survey. In International Cross- Domain Conference for Machine Learning and Knowledge Extraction, pp- 77-95. Springer, 2020.
Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. Proc. Computer Vision and Pattern Recognition (CVPR), IEEE, 2017.
Anand Rajaraman and Jeffrey David Ullman. Mining of massive datasets: Data mining (ch01). Min. Massive Datasets, 18:114-142, 2011.
Paramita Ray and Amlan Chakrabarti. A mixed approach of deep learning method and rule-based method improve aspect level sentiment analysis. Applied Computing and Informatics, 2020.
Cynthia Rudin. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature Machine Intelligence, 1(5):206-25 215, 2019.
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In European semantic web conference, pp. 593-607. Springer, 2018.
Julian Schrittwieser, loannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with learned model. Nature, 688(7839):604-000 4044 2020.
Mohit Shridhar, Xingdi Yuan, Mare-Alexandre Côté, Yonatan Bisk, Adam Trischler, and Matthew Hausknecht. Alfworld: Aligning text and embodied environments for interactive learning. arXiv preprint arXiv:2010.03766 2020.
Tianmin Shu, Caiming Xiong, and Richard Socher. Hierarchical and interpretable skill acquisition in multi-task 2017.
reinforcement learning. aiv preprint
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schritlwieser, Toannis Antonoglou, Veda Panneershelvam, Mare Lanctot, el al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
Shao-Hua Sun, Hyeonwoo Noh, Sriram Somasundaram, and Joseph Lim. Neural program synthesis from diverse demonstration videos. In International Conference on Machine Learning, pp. 4790 4799. PMLR, 2018.
Pelar Veličković, Guillem Cucurull, Aranixa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710.10003, 2017.
Abhinav Verma, Vijayaraghavan Murali, Rishabh Singh, Pushmeet Kohli, and Swarat Chaudhuri. Program- matically interpretable reinforcement learning. In International Conference on Machine Learning, pp. 6045-5054. PMLR, 2018.
Alexander Sasha Vezhnevets, Simon Osindero, Tom Schaul, Nicolas Heess, Max Jaderberg, David Silver, and Koray Kavukcuoglu. Feudal networks for hierarchical reinforcement learning. In International Conference on Machine Learning, pp. 3540 3549. PMLR, 2017.
Tong Wang. Gaining free or low-cost interpretability with interpretable partial substitute. In International Conference Machine Learning, pp.
PMLR, 2019.
16

---

Published in Transactions on Machine Learning Research (10/2022)
Tonghan Wang, Tarun Gupta, Anuj Mahajan, Bei Peng, Shimon Whiteson, and Chongjie Zhang. Rode:
Learning roles to decompose multi-agent tasks. orXiv preprinl arX::20010005223, 2020.
Vikram Waradpande, Daniel Kudenko, and Megha Khosla. Graph-based state representation for deep reinforcement learning. arx preprint or 2xix:2004.139000 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks?
arXiv preprint 181: 00820, 2018.
Seongjun Yun, Minbyul Jeong, Rachyun Kim, Jaewoo Kang, and Hyunwoo J Kim. Graph transformer networks. Advances in neural information processing systems, 32, 2019.
Mohammed Javeed Zaki. Scalable algorithms for association mining. IEEE transactions on knowledge and data engineering. 12(3):372-33) 2000.
Vinicius Zambaldi, David Raposo, Adam Santoro, Victor Bapst, Yujia Li, Igor Babuschkin, Karl Tuyls, David Reichert, Timothy Lillicrap, Edward Lockhart, et al. Deep reinforcement learning with relational inductive biases. 2018.
Quanshi Zhang, Ying Nian Wu, and Song-Chun Zhu. Interpretable convolutional neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 8827 8836, 2018.
Bolei Zhou, Aditya Khosla, Agata Lapedriza, Aude Oliva, and Antonio Torralba. Learning deep features for discriminative localization. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2921 2929, 2016.
Yang Zhou, Zachary While, and Evangelos Kalogerakis. Scenegraphnet: Neural message passing for 3d indoor scene augmentation. In Proceedings of the IEEE/CVF International Conference Computer Vision, pp. 7384-7392, 2019.
17


Reviews:
[{"review_id": "kwEbxk4L9E", "reviewer": "Reviewer_uHMN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The paper is well-written and easy to follow\n- The paper is complete and thorough. The proposed method is studied in-depth until reaching a working implementation on several graph games.\n- The idea of selecting an action in two stages, with only one stage that needs to be explainable, seems novel\n- The empirical results are very encouraging\n\nWeaknesses:\n\n- The biggest weakness, to me, is that the two parts of the paper (two-step selection process, then graph tasks) are distracting for each other. It is difficult to measure the applicability of the two-step action selection process to general RL, given that it is applied to such a specific kind of tasks. Much room in the paper is used to explain how graph nodes and edges are processed and embedded.\n- The background section should explain how graph neural networks work, given that (at that point in the paper) it seems that the agent will observe graphs as inputs. Then, in the Experiments section, it appears that fastText embeddings are used instead of graph snippets. Does it mean that no graph neural network is used? How are these things combined?\n- In Section 4.4.2, it is unclear of whether $D_k$ contains only demonstrations in which actions belonging to $A_k$ have been taken. This would make sense but is not stated in the paper.\n- Defining \"explainable\" is very difficult, and this paper lacks a bit in that regards. For instance, the experiments focus on generalization, and there is a discussion (that I don't fully understand by the way) about how explainable the learned rules are. It would have been interesting, for the learned policies in the experiments, to show the rules and provide arguments for their explainability.\n\nThe paper touches upon being careful when producing rules (for the action selector), so that applying the rules leads to a good policy. Relevant work is appropriately cited, but I humbly suggest this additional paper, not yet well-known:\n\nBonaert, G., Coppens, Y., Steckelmacher, D., & Nowe, A. (2020). Explainable Reinforcement Learning Through Goal-Based Interpretability.\n\nIt also describes a training procedure in which a DQN agent learns to perform a task (without graphs being used), then the policy is distilled in a rule-based system, that is then fine-tuned on the original task to ensure that the rules actually explain a high-quality policy, instead of blindly producing rules that may not match the actual behavior of the DQN agent in important states.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes an architecture and training method for Reinforcement Learning agents that need to perform well and be explainable. The action-selection procedure is modified to become two-step: first, a black-box approach (such as a neural network) maps a state to a category of action. Then, a rule-based action selector selects a particular action in that category of actions. The rules are human-understandable.\n\nThe paper is applied to rule-based games, such as following recipes (dicing a potato, etc). A second part of the paper (in addition to what is summarized above) explains how the authors managed to get an RL agent to learn such games, two times: one time with DQN to obtain a training dataset of state-action pairs, then a second time using the proposed two-step approach to produce an action pruner and an action selector.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "For a clear accept: removing everything related to graphs and focusing on the core contribution of the paper (or what seems to be it): the two-step action selection procedure. I would dream of seeing that applied to standard RL benchmarks, to see how actions can be organized in categories in practice, and how well it would apply to simple tasks like LunarLander, or more complicated ones such as continuous-actions Mujoco tasks (in which case the action selector should perform a regression)\n\nTo strengthen this version of the work: better background on graph neural networks, insights on how the first contribution can be applied to non-graph settings, and a better analysis of whether the produced explanations are actually explainable.", "broader_impact_concerns": "There is no broader impact concern.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "CZ4BNp2pbR", "reviewer": "Reviewer_gCx1", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1) Interpretability is an important aspect of using RL in real world applications, hence the motivation for the work is important.\n\nWeakness:\n1) The related works section is not adequately complete. For instance the authors should cite and discuss existing works which use similar ideas of two step action clustering and selection in the multi agent RL space for tractable learning and exploration: like: Maven [1] (uses a hierarchical action selection framework which learns diverse interpretable joint behaviours via latent space), Rode [2] (uses action pruning via role decomposition and subsequent selection), Uneven [3] (uses successor features for better exploration via two step process for task and action selection).\n2) The proposed method doesn't seem to provide interpretability by design, but instead seems to rely on the specific domains like text, VQA etc which facilitate interpretability (Viper [4] does not rely on such assumptions). Additional experiments on domains which are not natively interpretable should be carried out.\n3) How will the rule mining step work on non textual domains? (currently the approach seems very hand designed and fails to support the claim that it is a general interpretable RL approach). In general rule mining is plausible only for domains which are already interpretable.\n4) The writing needs to improve a lot and has to be made crisp, a lot of sections are too verbose and convey very little. There are several typos which should be corrected ex.: \"Therefore, we needs to label each state\", \"introducing new programms Verma et al.\",\"introduce some sorts of attention mechanisms\"\n5) How is the level of difficulty decided in TextWorld? a recipe size of 1 seems unconvincing for requiring a decomposed approach. There needs to be some brief discussion about the qualitative aspects of the domain.\n\n* [1] Maven: Multi-agent variational exploration, Mahajan et al 2019\n* [2] Rode: Learning roles to decompose multi-agent tasks, Wang et al 2021\n* [3] Uneven: Universal value exploration for multi-agent reinforcement learning, Gupta et al 2021\n* [4] Verifiable Reinforcement Learning via Policy Extraction, Bastani et al 2018\n", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes an ML pipeline for reinforcement learning using a two step approach in which the first involves pruning the possible actions and the second then picks an action from the pruned action set. Empirical analysis is done on the TextWorld domain along with 2 baselines.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Critical actionable changes:\nSee weakness section points 1,2,3,4.\n\nGood to have changes:\nSee weakness section points 5.", "broader_impact_concerns": "The authors should briefly discuss the ethical impacts of using the proposed interpretable RL based approach for real life settings (currently not present in the submission).", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "HXSfLIeSoj", "reviewer": "Reviewer_hPoo", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nPros / strengths:\n1. The paper is well written and the related work is adequate.\nThe figures in the paper well illustrate the algorithms.\n2. The algorithm combines the reinforcement learning & forward neural networks with existing rule-based methods. The latter part can be extended easily to other rule-based methods, where ppl can tune and interpret easily. I imagine this method will be more likely to be accepted by industrial applications.\n3. The algorithm is neat and simple, which allows it to be deployed easily without worrying too much about the underlying hardware infrastructure.\n4. The discussion section in the experiment session is very intuitive, interesting and inspiring.\n\nCons:\n1. Lack of baselines and ablation study.\nA lot of the design choices seem rather arbitrary. Why use graph neural networks with graph convolutional units? Why not graph transformers?\n\nSeveral modules are involved in the proposed algorithm. There’s a RL controller that learns an ok initial policy. Then there’s a gnn to distill the knowledge, and then there’s one specific rule based algorithm. How much contribution does each one of these modules provide? What happens if any one of the modules is removed or replaced with other modules?\n\n2. The problem is quite limited to the specific problem of TextWorld.\nThe algorithm itself seems quite general, which can handle sequential decision problems with graph input structures. But only Textworld is considered, which is a pity because I believe a lot of the other environments could have been considered such as [1]. I also believe there's a lot of different knowledge graph based problems that can be considered, though I cannot say for sure since I don’t have a related background.\n\n[1] Puig, Xavier, Tianmin Shu, Shuang Li, Zilin Wang, Yuan-Hong Liao, Joshua B. Tenenbaum, Sanja Fidler, and Antonio Torralba. \"Watch-And-Help: A Challenge for Social Perception and Human-AI Collaboration.\" In International Conference on Learning Representations. 2020.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "\nIn this paper, the authors propose to use a reinforcement learning controller to learn a good init action policy. \nThe learned policy is used to distill a graph neural network based action pruner.\nThe pruned action types are then further processed by the rule-based final action selector.\n\nIt provides a valid solution to the problem of TextWorld, and achieves better performance than some of the baselines.\n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "\nBased on the current version, I think I lean towards weak acceptance for this paper, mainly because it solves a very specific problem in a nice and simple way.\nI do worry about the novelty and completeness of the algorithm in terms of the values in machine learning.\nThese are some questions I have, and will potentially address some of my concerns and strengthen the work in quality.\n\n1. As mentioned in the pros and cons section, maybe the author can discuss some potential ablation study for the algorithm?\n2. Is it possible to apply the algorithm to other problems than TextWorld?\n3. Based on my understanding, the RL controller is fixed as the teacher during the second part of the training. And the GNN pruning can be only as good as the RL controller, which seems like a performance bottleneck. \nIs there a way that the algorithm will improve the pruner further with RL while also equipping it with the rule-based action selector?\n\n\n", "broader_impact_concerns": "\nThere’s no broader impact concerns as far as I can tell.\n", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The additional revisions very well addressed most of the reviewers drawbacks and concerns.  
Decision: Accept (poster)