Rule-Guided Reinforcement Learning Policy Evaluation and Improvement

1 Introduction

Deep reinforcement learning (RL) has shown impressive feats. Starting from deep Q-learning [Mnih et al., 2015], where a single network architecture successfully played dozens of Atari games, deep RL has moved on to more complex domains and achieved super-human performance in games, like Go [Silver et al., 2016] and chess [Silver et al., 2018], and it mastered StarCraft [Oriol Vinyals et al., 2019]. Despite the impressive success in winning strategy games, deploying deep RL agents faces challenges in other domains. First, the decision-making of RL agents needs to be more accurate, making it hard to trust their decisions. Second, successful applications are often not the result of RL alone.

A thorough analysis of an agent's behavior may help understand its "reasoning" - e.g., chess masters found that AlphaZero highly values king mobility [Nielsen, 2019]. Explainable AI (XAI) methods strive to alleviate the analysis of policies by providing human-understandable explanations of an RL agent's decision. Relating to the second point, AlphaZero combines RL with Monte Carlo tree search (MCTS) to better evaluate situations. Thus, it considers the application domain, as MCTS works well for decision-making in board games [Chaslot et al., 2008].

Contributions. We propose poLicy Evaluation GuIded By ruLEs (LEGIBLE), a rule-based framework to create explanations of an RL policy's decisions and to evaluate and improve the RL policy under consideration, supported by domain knowledge. LEGIBLE comprises three main methods that build upon each other. 1. Mining Rules: We first mine rules that partially represent the policy. These rules are split into positive, denoting action choices, and negative rules, denoting action avoidance in particular situations. They enable human comprehension of a policy's decisions and symbolic reasoning and manipulation. 2. Generalizing Rules: We propose an approach to generalize mined rules to other situations through domain knowledge about symmetries and relations known about the environments. Borrowing the concept from software testing, we formalize the generalization via metamorphic relations [Chen et al., 2018]. 3. Rule-Guided Execution: Finally, we propose to guide the execution of a policy in the RL environment with generalized rules, i.e., enforce the decisions prescribed by rules, which serves two purposes. 3.1. Evaluation: Rule-guided execution helps to identify weaknesses in the policy. If we find that enforcing generalized rules corresponding to a certain rule r improves the RL agent's performance, we can deduce that the original rule r is likely adequate. However, the policy has not learned to decide adequately in related situations, i.e., we identify a weakness in the policy's generalization. Additionally, the generalized rules explain the cause of the weakness. 3.2. Policy Improvement: Finally, guiding policy execution with the composition of generalized rules, which the evaluation deemed useful, creates a new policy that improves upon the original policy. We demonstrate these aspects of LEGIBLE in experiments with policies trained in six PAC-Man RL environments [DeNero and Klein, 2010] and five environments from Farama's highway-env [Leurent, 2018].

Related Work. Our work is related to explainable RL (XRL), runtime enforcement, and evaluation of RL policies. [Milani et al., 2024] provide an excellent survey on XRL including a taxonomy and evaluation criteria. Learning rules falls into the most popular taxonomic category of feature importance and the subcategory Convert Policy to an Interpretable Format. Although symbolic rules as an interpretable format are not popular yet, decision trees which are related to rules are often used [Bewley and Lawry, 2021; Guo and Wei, 2022; Bastani et al., 2018; Milani et al., 2022]. Several neuro-symbolic approaches have been proposed for RL, where neural networks encode symbolic relations and logical rules. Examples include neural logic machines [Dong et al., 2019] and neural logic RL [Jiang and Luo, 2019], and relational approaches [Delfosse et al., 2023; Zambaldi et al., 2018] that enable the extraction of symbolic information and rules from learned policies. In contrast to these works, we consider standard architectures used in deep RL and extract partial rule-based representations of learned policies. Moreover, we demonstrate the application of rules beyond explanations for evaluation and runtime enforcement.

There are two main strands of work in RL policy evaluation: off-policy evaluation (OPE) and testing of RL policies. OPE [Uehara et al., 2022; Chandak et al., 2021; Jiang and Li, 2016] estimates the expected performance of a new policy using existing data from a previously learned policy. Since we generate new data, our approach to evaluation is closer to RL testing [Tappler et al., 2022; Tappler et al., 2024b; Tappler et al., 2024a; Zolfagharian et al., 2023; Li et al., 2023; Biagiola and Tonella, 2024], which creates challenging situations to test policies in them. These approaches apply software testing concepts, like search-based testing, to RL. To our knowledge, we are the first to apply metamorphic testing in RL, which is popular for testing other machine-learning models [Zhang et al., 2022; Xie et al., 2011; Guo et al., 2020] due to its applicability when absolute correctness criteria are not available. To test policies, we perform rule-guided execution of policies, which can be considered a type of runtime enforcement [Falcone, 2010]. In RL, runtime enforcement has gained popularity in the form of shielding [Alshiekh et al., 2018; Odriozola-Olalde et al., 2023], which enforces pre-specified properties like safety. In contrast, we enforce generalizations of learned rules to evaluate these generalizations.

2 Preliminaries

2.1 Reinforcement Learning

An RL agent learns a decision-making policy for a task by trial and error. At each step, the agent observes the environment's state and performs an action, triggering a stochastic state transition. It then receives feedback in the form of a numerical value, called reward, telling it how well it is doing, and the new state of the environment. During training, the agent learns how to maximize the cumulative reward it gets.

Let ∆(S) denote a probability distribution over a set S. Formally, an agent interacts with a Markov decision process (MDP) M = ⟨S, s0, A, P, R⟩ consisting of a set of states S, an initial state s0 ∈ S, a set of actions A, a probabilistic transition function P : S ×A → ∆(S), and a reward function R : S × A × S → ∆(R). The agent's behavior is characterized by a policy π : S → ∆(A), defining a distribution over actions to take in given states. Executing a policy π within an environment modeled by an MDPMyields traces of the form s0, a0, r1, s1, . . . , an-1, rn, sn with ri ∼ R(si-1, ai-1, si), P(si, ai)(si+1) > 0, and π(si)(ai) > 0. Such a finite execution is also called an episode. The agent's goal is to learn a policy that maximizes the discounted cumulative reward R = E(∑∞i=0 γ i ri+1) for a discount factor γ ∈ [0, 1).

To handle large state spaces, RL algorithms often employ neural networks as function approximators, e.g., for stateaction value functions [Mnih et al., 2015]. Since we mostly focus on extracting symbolic knowledge from policies in this paper, we do not detail the specifics of RL algorithms.

State-Action Value Function. Q-learning [Watkins and Dayan, 1992] and its deep variants [Mnih et al., 2015; van Hasselt et al., 2016] are based on the notion of Qfunction, or state-action value function. This function is defined as Qπ(s, a) = E[∑∞i=0 γ i ri+1|s0 = s, a0 = a], i.e., it is the expected return after executing a in state s and then following policy π. We focus mainly on Q-learning agents and use the Q-function to identify actions that an agent avoids in a given situation, i.e., actions with low Q-values.

2.2 Explainable & Interpretable AI

Explainable AI (XAI) methods create human-understandable explanations of individual decisions or predictions of models that are otherwise not interpretable, like neural networks, while interpretability techniques commonly extract useful information, like interpretable surrogate models, from noninterpretable models [Molnar, 2022]. To enable human comprehension, explanations commonly focus on the most relevant factors leading to a decision, like the most important input features. This working principle makes XAI techniques good candidates for creating abstractions for symbolic AI. We use a model-agnostic XAI technique for explaining individual predictions, called LIME [Ribeiro et al., 2016], and we use rules as (partial) surrogate models of RL policies.

LIME. Treating the choice of action a through a policy π in state s as a classification task, LIME can learn a local interpretable surrogate model around s. It samples new data points around s and queries π to learn the surrogate model, which explains what features of s lead to the choice of a and provides weights describing the strength of influence. As we consider states that are vectors containing information about the environment, we use LIME for tabular data. In this case, it samples new values in the neighborhood of numerical features and values from a training set for categorical features.

We use the Python implementation of LIME [Marco Tulio Ribeiro et al., 2021], which provides an explanation for predicting every available class, i.e., for choosing every available action. Several alternatives to LIME exist, like SHAP [Lundberg and Lee, 2017], but we have chosen LIME as it is reasonably fast and showed promising results in experiments. Since it is model-agnostic and works for image and textual data, LIME enables us to easily adapt to changing representations of π and to handle additional types of features. Interpretability & Rules. RL interpretability is approached in different ways, e.g., post-hoc interpretability for a DRL policy π may be achieved by learning a decision tree policy from π through imitation learning [Bastani et al., 2018]. We learn rule-based representations of policies, which, like decision trees, enable manual comprehension and symbolic reasoning [Apt´e and Weiss, 1997]. The rules are of the form a ← c1, . . . , cn, specifying to take action a if conditions c1 to cn hold. We have chosen rules, as they conveniently enable learning partial representation of a policy. For rule learning, we use the algorithm RIPPER [Cohen, 1995], where we treat the selection of actions as a classification task from states to actions. To clearly distinguish between reinforcement learning and rule learning, we refer to the latter as rule mining.

2.3 Metamorphic Testing

Metamorphic testing (MT) [Chen et al., 2018] is a technique for generating test cases and deciding on test verdicts. It is based on metamorphic relations (MRs), which define a relation between a sequence of a program's inputs and the corresponding outputs. MRs express the output changes in response to input changes. Consider, e.g., a program implementing the factorial, an MR could be defined as ⟨(n, n + 1), (r, r · (n + 1))⟩, where the first pair represents two inputs and the second pair represents two outputs denoting that if n! = r then (n + 1)! = r · (n + 1) should hold. Note that MRs do not specify correctness criteria in absolute terms but as relations. This makes MT a popular choice for deciding on test verdicts in machine learning [Zhang et al., 2022], e.g., in image recognition [Dwarakanath et al., 2018]. While it is hardly possible to completely characterize a cat, MRs can express properties like if an image shows a cat, then a rotated version of that image still shows a cat. In this paper, we adapt MRs from programs to RL agents, by forming relations over states (inputs to the agent) and actions (outputs of the agent) to express domain knowledge. Unlike in MT, we do not make assumptions about the correctness of specific chosen actions.

3 LEGIBLE

This section presents an overview of poLicy Evaluation GuIded By ruLEs (LEGIBLE), our rule-based framework for policy evaluation and improvement, comprising the three main steps depicted in Fig. 1. Step 1 learns symbolic rules that (partially) capture the decision-making of a given deep RL policy. Rules are Horn clauses, where the head specifies an action and the body defines states in which the rule should be applied. We distinguish positive rules, for situations where the policy chooses a certain action, and negative rules describing situations where it avoids a certain action. Rule mining applies two types of criteria: (1) the rules should reflect what features are important to the decisions of the RL policy, and (2) the rules should be accurate and cover as many situations as possible, where we favor accuracy. Hence, mined rules explain which decisions are important and occur often.

Step 2 generalizes rules to new situations that are related to the originally covered situations through user-specified relations. For this purpose, we use metamorphic relations (MRs) [Chen et al., 2018] from software testing, which usually specify how program outputs should change in response to input changes. Likewise, we use them to specify how decisions should change in response to a change in the state. MRs generally need to be created manually and they reflect some domain knowledge about the environment, like symmetry constraints, i.e., through Step 2, we provide a method to introduce symbolic domain knowledge into RL.

Finally, in Step 3 we apply the generalized rules during executions of the RL policy under consideration. Actions prescribed by rules generalized from positive rules are enforced while actions of negative generalized rules are blocked. In this way, we determine which rules generalize to improved behavior in the RL environment. Conversely, such improvements reveal weaknesses in the RL policy since they show that the policy makes useful decisions in some specific situations but it does not generalize these decisions to all related situations. Hence, Step 3 provides a way to evaluate RL policies and a basis for policy improvements by enforcing sets of generalized rules that influence behavior positively.

Setting. For the remainder of this paper, let π be the greedy policy of a Q-learning-based agent and Q: S ×A → R be its Q-function. A state s is a vector in Rn , where n is the number of features, fi for i ∈ [1..n] denotes the ith feature, and f s i denotes its value in s. To enable rule learning, we consider environments with a discrete action space and discretize the state space by defining intervals for every feature separately. To simplify the presentation, we write f s i = k to denote f s i ∈ [li,k, ui,k] where [li,k, ui,k] is the kth interval for feature i.

Running Example. Figure 2 shows a small PAC-Man environment from [DeNero and Klein, 2010], which serves as a running example. The agent can move in the four cardinal directions or do nothing at every time step. Its goal is to eat all pellets (small dots). Colliding with ghosts terminates an episode unless they are vincible, which happens for a fixed amount of time after the agent eats a capsule (large dot). The observable states include information on the location of walls, the distance to ghosts, capsules, and pellets, the direction towards these objects, and other data. For efficient learning, we use a one-hot encoding for categorical features, e.g., features 9 to 12 describe the direction toward the closest pellet, where f s 9 = 1 means that the closest pellet is north.

The agent receives a reward of 10 for eating a pellet, 200 for eating a ghost (collision when vincible), 500 for completing the level, -500 for colliding with an invincible ghost, and -1 every time step to encourage fast completion.

4 Step 1: Rule Mining

To create training data for rule mining, we execute the agent in its environment for nrule episodes to sample traces, i.e., state-action-reward sequences. From these traces, we collect all observed state-action pairs (s, a) ∈ S × A in a multiset E to which we refer as experiences. We treat rule mining as a classification problem from states to actions based on training data E, where we aim to learn rules that (1) represent what is important to the agent's decisions and that (2) are accurate and have high coverage. In the following, we detail the form of rules we consider and how we learn them.

Rules. A rule ρ is of the form:

⊗ ∈ {+,-} is the rule polarity, and I ⊆ [1..n] is a set of (feature) indices. We refer to the conjunction of conditions as the rule body, denoted body(ρ), and to the action consequent as the rule head. Given a state s which satisfies ∧i∈I vi = f s i , we say that ρ triggers in s, denoted s |= ρ. If ⊗ = -, ρ is a negative rule, denoting action a is avoided if s |= ρ. A positive rule with ⊗ = + denotes that a should be taken.

Feature Importance. To determine which features are important to the policy's decision, we select nfeat experiences from E and apply LIME to generate explanations for the decisions of π. The explanations quantify the importance of a feature fi to perform or not perform an action a. For each fi, we compute the sum of importance values from the nfeat explanations, which we denote by imp(⊗, a, fi), representing the importance of feature fi to take or avoid a.

Mining Rules. We apply the rule learning algorithm RIPPER [Cohen, 1995] for every combination of action and rule polarity individually. This approach enables more effective mining of negative rules compared to posing rule mining as a multi-class classification problem for all actions. Hence, we select two datasets from E for every action-polarity combination, which rules shall distinguish: the inclusion dataset inc(a,⊗) containing positive examples and the exclusion dataset exc(a,⊗). To account for feature importance, we adapt RIPPER's rule growing. Instead of solely targeting coverage by optimizing FOIL's information gain during rule East growing, we maximize the product of FOIL's information gain and feature importance imp(⊗, a, fi).

Figure 3: State-action pairs related by fr = ⟨0, 2, 62, 64, =⟩.

The inclusion dataset inc(a,+) for mining positive rules contains all (s, a) from E, i.e., experience matching action a, and the exclusion dataset contains all (s, a′ ) from E s.t. a′ ̸= a. To mine negative rules, we add all (s, a′ ) where a′ = argmina Q(s, a) in inc(a,+) and we add all (s, a) to exc(a,-). Following the rule mining through RIPPER, we filter rules by imposing bounds on minimal accuracy and coverage. We evaluate the accuracy of a rule by checking if it agrees with the experiences from a validation set. Coverage refers to the ratio of times that a rule triggers, which is a common optimization criterion of rule learning algorithms.

Running Example. In the PAC-Man environment, we learn rules, such as ρ1 = -action(0) ← f62 = 0 and ρ2 = +action(0) ← f9 = 1 ∧ f50 = 1 ∧ f62 = 1 ∧ f65 = 1. Both predicate on action 0, i.e., going north. Rule ρ1 says that PAC-Man avoids trying to go north if there is a wall, as f62 = 0 means that going north is not possible. The second rule ρ2 says that the agent learned to go north if there is a pellet in the north direction (f9 = 1), Ghost 2 is west (f50 = 1), and there is no wall to the north (f62 = 1) and west (f65 = 1).

5 Step 2: Rule Generalization

The rules provide insights into decisions that the policy learned to be beneficial. The intuition behind rule generalization is that often there are symmetries in the environment and the agent may have learned how to act in one situation, but not in corresponding symmetrical situations. More generally, situations are often related through relations that can be expressed symbolically. Borrowing the concept from software testing, we refer to these symbolic relations as metamorphic relations (MRs). We define MRs for RL based on feature relations that relate actions and individual features of states.

Definition 1. A feature relation fr is a tuple ⟨a, a′ , i, j,R⟩ with R ⊆ R×R describing a relation between features i and j in state-action pairs. Two state-action pairs (s1, a1) and (s2, a2) are feature-related by fr denoted (s1, a1) fr (s2, a2) iff a1 = a∧a2 = a′ ∧(f s1 i , f s2 j ) ∈ R. Ametamorphic relation mr for RL is a set of feature relations defined on the same actions a and a′ . Given sa1 = (s1, a1) and sa2 = (s2, a2), we define sa1 mr sa2 iff sa1 fr sa2 for all fr ∈ mr, i.e., an MR relates multiple pairs of features of state-action pairs.

Running Example. Figure 3 shows two PAC-Man stateaction pairs related by ⟨0, 2, 62, 64, =⟩, where = simply denotes the equality relation. On the left, PAC-Man goes north action with action 0 and there is no wall to the north, represented by f s 1 62 = 1. On the right, PAC-Man goes east with action 2 and there is no wall to the east f s 2 64 = 1, i.e., we have f s 1 62 = f s 2 64 satisfying the relation from fr.

Input: Q-function Q, set of gen. rules G, # eval. episodes n Output: Average Cumulative Reward 1: Rews ← ⟨⟩ 2: for i ← 1 to n do 3: s ← RESET(), rew ← 0 4: while s not terminal do 5: Gt ← {(action(r), polarity(r)) | r ∈ G, s |= r} 6: if |{(a, +) ∈ Gt}| = 1 then 7: act ← a 8: else 9: q ← Q(s, ·) 10: q(s, a) ← -∞ for (a, -) ∈ Gt 11: act ← arg maxa q(s, a) 12: s, r ← STEP(s, act), rew ← rew + r 13: APPEND(Rews, rew) 14: return mean(Rews), stderr(Rews)

We define MRs based on feature relations to enable convenient, compositional definitions and extend them to rules as follows. Let fr = ⟨a, a′ , j, k,R⟩, ρ1 = ⊗1action(a1) ← ∧i∈I1 fi = vi1, and ρ2 = ⊗2action(a2) ← ∧i∈I2 fi = vi2: ρ1 fr ρ2 iff ⊗1 = ⊗2, a1 = a, a2 = a′ , and either fj = x ∈ body(ρ1) and fk = y ∈ body(ρ2) such that (x, y) ∈ R or j /∈ I1 and k /∈ I2. Rule bodies must either include facts satisfying the relation R, or they should not predicate on the respective features. Analogously to states, we extend MRs to rules denoted by ρ1 mr ρ2. Through sets of MRs M, we automatically generalize each positive and negative rule ρj to a set of positive or negative rules given by the fixed point of Mgen(ρj) = {ρj} ∪ ⋃{Mgen(ρ) | ρj mr ρ, mr ∈ M}.

Running Example. We illustrate rule generalization with rule ρ1 = -action(0) ← f62 = 0 and feature relation fr = ⟨0, 2, 62, 64,=⟩ from above. An MR mr = {fr} including only fr describes a 90-degree clockwise rotation of the action and the only relevant feature from north to east. Action 0 and 2 describe going north and east, respectively. Features 62 and 64 indicate the absence of a wall to the north and east, respectively, e.g., f64 = 0 means that there is a wall to the east. Hence, if ρ2 = -action(2) ← f64 = 0 then ρ1 mr ρ2, because ρ1 fr ρ2, which holds because polarity(ρ1) = polarity(ρ2), head(ρ1) = 0, head(ρ2) = 2, and f62 = 0 ∈ body(ρ1), f64 = 0 ∈ body(ρ2) with 0 = 0. The rule ρ2 can be automatically generated and states to not go east if there is a wall. Enforcing it may improve performance if the agent has not learned to generalize from ρ1 to ρ2, because trying to go into a wall results in a reward of -1 as the agent stays in its location in such a case.

6 Step 3: Guiding Agents with Rules

To evaluate π, we propose to first execute π without rule guidance and then guide π with each rule set Mgen(ρj ) separately for a set M of MRs. By comparing the gained cumulative reward, we determine which generalized rules improve performance and thus reveal weaknesses of π.

Algorithm 1 monitors the execution of π for n episodes and enforces rules if they trigger. It assumes that the environment provides RESET and STEP operations, which are commonly part of the interface to RL environments, like the Gymnasium API [Towers et al., 2024]. After resetting the environment to start an episode, in every step, Line 5 checks which rules trigger. If a single positive rule triggers (Line 6), we enforce it. Otherwise - there is no positive rule or a conflict between positive rules - we disable all actions of negative rules in Line 10 by setting their Q-values to negative infinity. After that, we choose the action with the highest Q-value or a random action if all actions have been disabled. Furthermore, we could add additional randomness to the action choices. Finally, Algorithm 1 returns the average cumulative reward and the corresponding standard error. While generalization does not change rule polarity, Algorithm 1 supports combining rules generalized from rules with different polarity.

7 Experiments

This section presents experiments on the application of learned and generalized rules. First, we show how generalized rules help detect weaknesses in RL policies through rule-guided execution and how rules can explain the identified weaknesses. After that, we demonstrate the RL policy improvement through rule-guided execution.

Setup and Environment. All experiments are based on RL policies trained in six PAC-Man levels [DeNero and Klein, 2010] and five highway-env [Leurent, 2018] environments using stable-baselines3 [Raffin et al., 2021]. The PAC-Man levels differ in size (small, medium, and original) and the presence of capsules. We trained DQN [Mnih et al., 2015] policies for 2.5 · 106 steps in the small and medium PAC-Man environments with 69-dimensional states and for 5 · 106 steps in the original-sized environments with 117dimensional states. In highway-env, we trained DQN policies for 5 · 105 steps to navigate in driving scenarios, like merging onto a highway. We configured highway-env to create observations relative to the ego vehicle, comprising 7 properties of the ten closest vehicles, like their relative positions. Every training run is repeated five times and the resulting policies provide the basis for the experiments below. Code and data from the experiments are available at https://doi.org/10.6084/m9.figshare.28569017.

We mine rules for all environments using the same setup, except for the discretization of states. In the PAC-Man environments, we use the decile discretization provided by LIME [Marco Tulio Ribeiro et al., 2021], which discretizes each numerical feature into intervals corresponding to deciles calculated from the data. Categorical features, like cardinal directions to the closest food, are left unchanged. The highway-env environments do not include categorical features and there we normalize and discretize each feature into ten intervals. For both types of environments, we sample nrule = 600 episodes to generate experiences for rule mining and impose a minimal accuracy of 0.9 and a minimal coverage of 0.01 on rules, discarding all other rules.

For the remainder of this section, let π denote a trained policy, R be a set of rules learned from π, and M be a set of MRs. The MRs for PAC-Man encode 90-degree clockwise turns from every cardinal direction, i.e., from every rule, we generate four rules, including the original rule. The highway-env MRs generalize rules to other vehicles occurring in observations, i.e., from a rule with conditions on the first vehicle, we generate rules conditioned on the other vehicles. Furthermore, the MRs encode symmetry constraints, e.g. generalizing rules for changing to the left lane to rules for changing to the right lane and vice versa.

7.1 IdentifyingWeaknesses

With the first set of experiments, we approach the research question RQ1: Does rule-guided execution effectively reveal weaknesses in a trained policy? We consider policy weaknesses as decisions where enforcing a rule improves performance, i.e., rule-guided execution detects decisions that could be improved. As a benchmark for performance, we compare against the average cumulative reward crπ gained by π without rule guidance. To identify weaknesses in π, we propose to generalize each rule r ∈ R to Rg = Mgen(r) individually and guide the execution of π with Rg using Algorithm 1. We perform n = 100 evaluation episodes in highway-env and n = 250 evaluation episodes in the PAC-Man environments. Rg reveals a weakness if the cumulative rewards from rule-guided execution are significantly larger than those of unguided execution, which we determine using a Welch test [Welch, 1947] and a p-value threshold of 0.05.

Baselines. We are the first to propose MT for RL, therefore we compare MT to two random baselines. The first baseline, random testing (RT), blocks or enforces randomly chosen actions during policy execution in k percent of the states. We randomly assign each of the k policy changes to approximately one percent of the state space, such that if we visit a state twice the same change happens. In the experiments, we performed 100 RT evaluations where we only blocked actions and 100 evaluations where only enforced actions. We set k = 3 since we found that low values are more effective at detecting weaknesses. Each evaluation compares against the average cumulative reward crπ from unguided execution.

Additionally, we use another random baseline, which we call random rules (RR). For RR, we randomly generate rule sets instead of generating them via MRs and execute Algorithm 1, i.e., RR serves as an ablation study to study the impact of MRs. The random generation uses information extracted from mined rules by creating rules with the same distribution of rule lengths and rule polarities, and by using the feature values found in the mined rules. Additionally, rule sets created for RR are of similar size as the rule sets created using MRs. Hence, the random rules benefit from information extracted from policies, but not from domain knowledge. Results. Tables 1 and 2 show evaluation results for the five base policies trained in each environment. For each RT, RR, and rule-guided execution supported by MRs, denoted as metamorphic testing (MT), the tables show the mean ratio of evaluations that detected weaknesses from five repetitions. The tables additionally show the number of evaluations for RR and MT (for RT they are fixed to two times 100), i.e., the number of generalized rule sets Rg. We can see that on average 5 to 24 percent of the MT evaluations reveal weaknesses. This is consistently higher than RT, especially in PAC-Man environments, where RT rarely reveals weaknesses. In contrast, RR reveals more weaknesses than MT in three cases where it substantially lees weaknesses in the other eight environments. We can answer RQ1 positively, as rule-guided execution consistently revealed weaknesses in the examined policies, both through RR and MT. We can further deduce that domain knowledge helps since MT performed better overall. In the cases, where RR performed better than MT, either our MRs may not optimally represent relations that hold in the environment or the policy under test generalizes well, but includes other issues that RR detects. MT further improves upon RR as it facilitates explanations, as the rules within a rule set are related. If a rule set Rg reveals weakness, we know that the cause is linked to the original rule from which Rg was generated and to the MRs used for generation. Beyond that, the good performance of RR suggests that search-based approaches, which are popular in RL testing [Zolfagharian et al., 2023; Tappler et al., 2022], might be viable for rule generation.

Explaining Weaknesses. We illustrate explaining policy weaknesses with two cases from the PAC-Man levels small and original with capsules. In both cases, the generalization of the following simple rules increases performance:

The feature indices differ among the environments, but both rules can be interpreted as "don't go north if there is no food and there is a wall to the north". Generalizations to other directions are safe to apply, yet the policies have not picked up on them, thus enforcing them improves performance. However, we found that the policies have learned stronger versions of these rules, e.g., in the environment original, we learned related rules with additional constraints: -action(1) ← f2 = 0 ∧ f9 = 0 ∧ f10 = 0 ∧ f11 = 1 ∧ f88 = 0 ∧ f111 = 0 and -action(3) ← f5 = 0 ∧ f10 = 1 ∧ f12 = 0 ∧ f113 = 0. Hence, rule-guided execution points to situations where the policy learned suboptimal decisions.

Algorithm 2 Greedy rule selection for policy improvement.

7.2 Policy Improvements

The remaining experiments focus on policy improvement through rule-guided execution, where we tackle Research Question RQ2: Can guidance with compositions of rule sets improve RL policies? For this purpose, we assume to have already evaluated π with all generated sets of rules Rg individually. To improve π, we propose to compose rule sets (RS) that reveal weaknesses without overconstraining the policy. Below, we present experiments, where we first greedily selected rule compositions RT through Algorithm 2.

Table 3 and Table 4 show the mean cumulative reward of non-rule-guided execution and execution guided by RT using Algorithm 1, again averaged over five repetitions. The tables also show the corresponding standard error of the estimate and how many rule sets have been composed to create RT. We performed the non-rule-guided execution with the base policies from which we mined rules and with policies trained twice as long, e.g., policies for highway-env were trained for 106 steps. We can see that rule-guided execution always improved the base reward substantially, except in the intersection environment, where the improvement is only marginal on average. In other cases, we see larger improvements, e.g., 274 percent in the highway-fast environment. We can further see that extended training did not improve the reward in many environments (PAC-Man) and only slightly in others (highway-env). In all cases, rule-guided execution yields larger improvements, thus it provides value that cannot be gained from more training. Moreover, the greedy selection of rules always composed multiple rule sets to create RT to improve the policy under consideration. Hence, we can answer RQ2 positively.

8 Conclusion

We propose LEGIBLE, a rule-based framework for evaluating, explaining, and improving RL policies. After learning rules from the most important policy decisions, we use highlevel domain knowledge to generalize learned rules to other related situations. For this purpose, we leverage MRs [Chen et al., 2018] to express relations like symmetries that hold in the considered environment. By executing policies guided by generalized rules, we identify weaknesses, where a policy learned to behave adequately in a particular situation, but not in related situations. That is, we find cases where RL policies fail to generalize. In these cases, the generalized rules and applied MRs explain the found weaknesses. LEGIBLE provides a basis for policy improvement, by enforcing sets of generalized rules, which were found to improve performance. In experiments with deep RL policies trained in six PAC-Man environments [DeNero and Klein, 2010] and in five highway-env [Leurent, 2018] environments, LEGIBLE revealed weaknesses in all policies, which are explained by the learned and generalized rules. Rule-guided execution improved the average cumulative reward by up to 273%.

LEGIBLE enables the integration of domain knowledge into RL policies and our evaluation approach is the first metamorphic testing (MT) approach for RL. In contrast to existing work on RL testing [Tappler et al., 2022; Zolfagharian et al., 2023; Li et al., 2023; Biagiola and Tonella, 2024], which brings the agent into challenging environment states, we take an agent-centric view, evaluating changes in the agent's decisions. By generalizing decisions learned from a policy, we ensure that generalized decisions are learnable.

In future work, we will investigate how to integrate other types of domain knowledge, e.g., by expressing temporal dependencies via restraining bolts [Giacomo et al., 2020]. As our work is complementary to existing RL testing approaches, we will combine MT with approaches that focus on the environment, like search-based testing [Tappler et al., 2022; Zolfagharian et al., 2023; Biagiola and Tonella, 2024]. Finally, we will work on a seamless integration of generalized rules into RL policies. Specifically, we are exploring how to integrate improvements resulting from rules into DRL policies, without needing to enforce them explicitly. To this end, we consider transfer learning [Torrey and Shavlik, 2010] and imitation learning as a basis [Hussein et al., 2017].

Acknowledgments

The project leading to this application has received funding from the European Union's Horizon 2020 research and innovation programme under grant agreement No 101034440. This work has further been funded by the Vienna Science and Technology Fund (WWTF) [10.47379/ICT22-023], [10.47379/ICT19018], [10.47379/ICT20058].