This paper presents an agent-based hybrid symbolic/subsymbolic learning approach as a basic model for the human ability of quickly recognizing and exploiting heuristic rules in an initially unknown environment. Instead of mechanically iterating a task until the optimal policy was found (as usually done by common Reinforcement Learning techniques), the agent finds heuristics expressed by symbolic knowledge bases which allow for an intelligent exploitation of knowledge gained from few experiences. For this purpose, a measure is proposed which allows an agent to decide on its own at which point during the learning process, its decisions should rely on the recognized heuristics rather than on a learned state-action pair representation. The approach will be evaluated both in the context of several grid world scenarios and a game from the GVGAI framework. It will be shown that our approach outperforms standard Q-Learning in the selected scenarios and arguments will be provided that also other agent-based machine learning techniques could profit from the proposed approach.
Common machine learning techniques used in the context
of learning agents (e. g., Reinforcement Learning based
approaches like Q-Learning
Humans, in contrast, are known for successfully applying rough heuristics learned from very few examples. This, of course, can lead to wrong decisions (see, e. g., (Do¨rner 1992) for several examples), however, in the common cases many problems can be quickly solved by applying such heuristics derived from few examples. One reason for that is, that many problem domains (e. g., games) are geared towards the commonsense human way of thinking, and these kinds of problems can therefore be quickly solved by exploiting such heuristics.
In this paper, we propose a hybrid symbolic/sub-symbolic
agent model which is able to autonomously find and exploit
useful heuristics in a previously unknown environment.
During a Reinforcement Learning process, the agent creates a
symbolic knowledge base from learned experiences which
comprises rule-based knowledge on multiple levels of
abstraction as a model for heuristics. We do not incorporate
any a priori knowledge (as done e. g. in
A hybrid symbolic/sub-symbolic agent model which incorporates both symbolic rule-based knowledge and weighted state-action pair representations learned by a sub-symbolic learning approach.
An approach for estimating the subjective structural
complexity of a previously unknown environment from an
agent perspective during a learning process (based on a
“commonsense” measure for strategic depth
Compared to our previous works on knowledge base
extraction presented in
As a side-product, the resulting agent model is still able
to explain the learned knowledge and the made decisions
to some extent at any point during the learning process, as
described in
In Section 2 related similar approaches will be discussed.
A brief introduction to the fundamental preliminary works
will be given in Section 3. The agent model will be
introduced in Section 4. In Section 5 the model will be
evaluated in the context of several simple grid world
scenarios and later in different levels of a game from the
General Video Game Playing Artificial Intelligence (GVGAI)
framework, which is usually used for the GVGAI
competition where agents have to compete in playing previously
unknown video games
Several attempts have been made so far to closer relate
symbolic knowledge representation and sub-symbolic machine
learning approaches in the context of agents. The basic ideas
can be roughly assigned to one of the following groups
(representatives for every group will be discussed subsequently):
1. Extraction techniques to gain different knowledge
representations (e. g., propositional rules) learned from data
through machine learning techniques
2. Methods to integrate a priori knowledge into machine
learning approaches to support the learning process (e. g.,
by shaping the search space with a priori knowledge and
later refining this knowledge with learning techniques)
3. Cognitive architectures that combine 1. and 2.
Representatives of the first group are, e. g.,
As representatives for the second group, e. g.,
The third group is represented, e. g., by models such as
CLARION
This section introduces the two preliminary works needed
for our approach: First, the concept of exception-tolerant
Hierarchical Knowledge Bases (HKBs)
To introduce HKBs and how they can be learned, we closely
follow
This section only provides the main definitions needed to understand the basic idea of HKBs. For more details on HKBs, the reader should refer to the original literature. Basics of the Agent Model We consider an agent which is learning a policy by acting autonomously in a previously unknown environment. The agent is equipped with n sensors through which it can perceive its current state in the environment. The agent is able to perform actions from a predefined action space and can furthermore perceive, whether or not the performed actions were good, in form of (numeric) rewards. The perceived rewards are then used to learn a weighted state-action pair representation where the weights determine which action has to be performed, given a perceived state (usually the one with the highest weight).
More formally, in such a representation, a state s is an
element of a multi-dimensional state space S = S1 ::: Sn
where n is the number of the agent’s sensors (through which
the agent is able to perceive its state in the environment)
1Note that in
2Note that the used learning approach is not of importance as long as it results in a weighted state-action pair representation, where the weights determine which action has to be chosen given a perceived state (usually the one with the highest weight). asm1a;:x::;sn = arg max qs1;:::;sn;a0 ).
a02A and every Si is a set of possible sensor values of the corresponding sensor. Furthermore, the agent selects actions from a predefined action set A and the learned weights are stored in a multi-dimensional matrix Q^ = (qs1;:::;sn;a) with si 2 Si and a 2 A. The weights can be learned by different machine learning approaches, provided that the learning approach converges such that given a state, the highest weight determines the best action to be selected (i. e.,
An HKB consists of rules which are organized on
different levels of abstraction. In contrast to Exception Lists
plete rules and generalized rules are of the form p ) a [w ], where p is either a complete state (in case of an complete rule) or a partial state (in case of a generalized rule), the conclusion a 2 A is an action of an agent’s action space A and w 2 [0; 1] is the rule’s weight.
Thus, complete rules map complete states to actions and generalized rules map partial states to actions. An HKB can now be defined as follows:
2 Ri is of length jS j = i Definition 3 (Exception-Tolerant Hierarchical Knowledge Base) An exception-tolerant Hierarchical Knowledge Base (HKB) is an ordered set KB := fR1; :::; Rn+1g of n + 1 rule sets, where n is the number of sensors (i. e., the number of state space dimensions). Every set Ri<n+1 contains generalized rules and the set Rn+1 contains complete rules, such that every premise p = Vs2S s of a rule 1.
According to Definition 3, the set R1 contains the most general rules (with empty premises) and the set Rn+1 contains the most specific (i. e., complete) rules.
For the relations of rules, the term of needed exception
will be used, according to the following definition (cf.
eaxcctieopntioan taosacrounlcelusi2onRajnd1 wweiitghhptrewmi,seif pS = VSs2Sansd, a 6= a . The exception is needed, if there exists no other rule 2 Rj 1 with premise p = V s and action a as conclusion where S S , a = a sa2nSd w > w . 3.2
An HKB can be extracted from a weighted state-action
pair representation Q^ (that is learned, e. g., through a
Reinforcement Learning technique) using the following
approach
The approach takes a weighted state-action pair representation Q^ as input and returns an HKB KBQ^ which reflects the knowledge contained in Q^ by performing the following steps: 1. Initial creation of rule sets: In the first step, the multiple abstraction levels R1; :::; Rn+1 of the knowledge base are initially filled with rules. We only consider state-action pairs here that contribute to the best policy found during the learning process so far.4 2. Removal of worse rules: In all sets Rj , a rule 2 Rj is removed, if there exists another rule 2 Rj with the same partial state as premise having a higher weight (i. e., in every set Rj only the best rules for a given partial state are kept). 3. Removal of worse more specific rules: In all sets Rj>1, a rule 2 Rj with premise p = Vs2S s, conclusion a and weight w is removed, if there exists a more general rule 2 Rj0<j with premise p = Vs2S s where S S = fs1; :::; sj 1g and weight w w . 4. Removal of too specific rules: In all sets Rj , a rule 2 Rj>1 with premise p = Vs2S and conclusion a is removed, if there exists a more general rule 2 Rj0<j with the same action a = a as conclusion and with premise p = V s where S S = fs1; :::; sj 1g and if is not asn2eSeded exception to a rule 2 Rj 1. 5. Optional filter step: Optionally, filters may be applied to filter out further rules which are, e. g., helpful to explain the knowledge contained in Q^ through the optimal found policy so far, but which are not needed for reasoning later.
After performing these steps on Q^, the knowledge base KBQ^ comprises all sets Rj 6= ; with the extracted rules representing the implicit knowledge contained in the learned weights of Q^ in a compact way.
Reasoning on HKBs A reasoning algorithm on HKBs
was proposed in
4Furthermore, since the number of possible premises of the
rules can grow drastically with the size of the given problem
instance, an efficient algorithm has to be used here. An attempt
for efficiently preselecting the rules using adapted ideas from the
APRIORI algorithm
Due to the possibility of falling back to more general rules in case no matching rule could be found for the given sensor values, the reasoning mechanism on an HKB allows for drawing meaningful conclusions over states that have not been seen before by an agent. The idea that a more general rule serves as a rough heuristic for unknown states (for which no better knowledge is available) will later contribute to accelerate the learning process. 3.3
Based on an HKB, in
n+1 ds(KB; S) := X i=1
n i 1 bi 1
P jRij
Q jSj jSjS=i S1 S2S ; (1) where n + 1 = jKBj = jSj + 1 is the number of levels in KB, b is a weighting constant, and Ri 2 KB is the i-th level of KB.
As rules on a level Rj>1 can be considered exceptions to the rules on level Rj 1, the intuition behind ds is that it measures the weighted relative number of rules (hence, exceptions) represented by an HKB.
In
S, n, b and ds be as in Definition 5. Then the normalized strategic depth is defined as a function ds(KB; S) :=
Pn+1 i=1 ds(KB; S)
n i 1 bi 1 : (2)
In the following, ds will be used in our agent model to allow the agent to estimate subjectively when it could be useful to exploit heuristics during a learning process in an a priori unknown environment: If ds falls below a certain threshold th then this indicates that heuristics could possibly be applied successfully.
The intuition behind this is that the (normalized) strategic depth based on an HKB which was extracted from a weighted state-action pair representation learned by an agent, will successively decrease as the agent’s learning process progresses: Since the agent’s knowledge about the problem increases, the problem appears successively less complex to the agent and the subjectively measures normalized strategy depth converges to the de facto strategic depth of the task to be learned (i. e., the strategic depth according to the HKB of the optimal policy to solve the task). We will demonstrate this in the following on several examples.
We consider four different grid worlds of different structural
complexities where an agent has to learn to navigate from a
starting point A to a target point B (see Figure 2). We use
standard Q-Learning
The subjective strategic depth decreases in general as the learning process progresses, since the agent’s knowledge about the scenario increases, and therefore the scenarios appears to be simpler to the agent. (In case of the fourth scenario, after the first runs, the agent seems to underestimate the depth of the scenario, since the scenario locally has straight path structures that form together a more complex path from a global point of view.) 4
This section introduces our model of a learning agent which is able to determine and exploit heuristics based on HKBs during a learning process in a previously unknown environment. In our agent model, a sub-symbolic learning approach can be used to learn weighted state-action pairs (where the maximum weight determines the preferred action, given a state). Figure 1 illustrates the main ideas of our agent model which mainly consists of two parts: an initialization part which is executed every time before a new learning episode starts, and a common agent cycle which is executed every time step. In the former, the agent decides, whether it relies its decisions on the weighted state-action pairs (represented by the Q^ matrix) or on the heuristics (represented by the current Percepts ; Reward Set action selection Set HKB action selection if HKB action selection and glob. reward < max. glob. reward if no random action (with prob. 1 ) if action selection
Agent if
< th if HKB action
selection Extract HKB
HKB
Initialization (executed before a new episode starts) Agent cycle (executed every time step) Environment
Update Weights if random action (with prob. ) Random action selection Action selection by Action selection by HKB
Action a extracted HKB) in the upcoming learning episode. This decision is made depending on the ds value calculated from the current extracted HKB.
In the latter, the agent either chooses a random action (for exploration purpose) or decides to choose its action according to the Q^ matrix or the extracted HKB, respectively, depending on the decision made during the initialization. Note that in Figure 1, components belonging to the sub-symbolic learning approach are indicated by a gray coloring, whereas those parts belonging to our heuristics extension are colored white. The gray parts could be replaced by a different learning approach.
5
This Section first evaluates the approach in the four grid
world scenarios from Figure 2 in Section 3.3. Later, the
approach will be evaluated additionally in a more realistic
example: a game from the GVGAI framework
We run the four grid world Scenarios from Figure 2 in Section 3.3 for 50 runs each and measure the percentage of how many times the optimal policy was found by the agent over 200 repetitions of the experiment. As learning approach we use again Q-Learning with the same parameters used for measuring the subjective strategic depth at the end of Section 3.3. As threshold parameter to determine the exploitation of found heuristics by means of the subjective strategic depth ds, we choose a threshold of th = 0:2. According to Figure 2, this means that—in average—the agent would try to exploit the found heuristics after 25 runs in case of the first scenario, 75 runs in case of the second scenario and 100 runs in case of the third scenario.
For the second and the third scenario, this may sound confusing since we perform a total number of 50 runs only. However, the reader should be aware that Figure 2 shows the average development of ds measure and thus there are enough cases where the agent individually decides to exploit a found heuristic that leads to an optimal policy.
As for the fourth scenario, the agent never considers to exploit any heuristics, since the subjective strategic depth does not decrease below th = 0:2. This can be interpreted in a way that the scenario comprises too many exceptions, such that an exploitation of heuristics does not make sense from the agent’s point of view (this point of view is in fact what the parameter th controls, depending on whether the desired agent should be more “heuristics-affine” or more “conservative”). Table 1 contains the comparison of our agent model (a) (b) (c) (d) against a standard Q-Learning agent with the same parameters for the learning part. In addition, for reasons of comparison, Table 1 also provides results of a heuristics-only version of the agent model5, where the agent was enforced to rely its decisions always on the extracted heuristics (i. e., in the initialization phase in Figure 1 the action selection mode is always set to HKB action selection and the weights contained in the Q^ matrix are never considered directly for action selection in the agent cycle).
As can be seen in Table 1, standard Q-Learning rarely manages to solve the grid worlds during the first 50 runs, whereas our heuristics approach clearly outperforms these results. As for the heuristics-only version, the results are slightly worse: This seems to be the case, since the agent starts too early to rely its decisions on the heuristics (which are nearly random in the beginning of the learning process). This may prevent the agent from further exploring the environment to an adequate extent and may result in local optimal policies.
One could argue that standard Q-Learning is a rather old
approach and there are nowadays more elaborate learning
approaches available. However, if a better learning approach
will be chosen in our setup (better in the sense that it will
converge faster to the optimal policy), the extracted HKBs
and hence the measure ds will be more accurate as well and
therefore, better heuristics could be exploited earlier during
the learning process. This means that in our approach, both
the heuristics and the measure ds (to decide when to exploit
them) will improve with the quality of the learning approach
used for the agent.
We evaluate the agent model now in a more realistic
example by consider the game Camel Race from the GVGAI
framework
The agent’s state space is described by the sensor value sets SxC1 SxC2 SyC2 SxC3 containing the coordinates of the camels in the game (where C1; :::; C3 correspond to the three camels, C2 is the camel in the middle controlled by the agent and C1; C3 only move in x direction) and A = fup; down; left; right; noneg are the five actions that can be performed by the agent. As reward, the agent perceives the current distance to the fastest opponent camel in x direction.
Even if the game is rather simple, it has an interesting aspect: Due to the dynamics of the environment caused by the movement of the two opponent camels, our agent perceives new and previously unseen states in nearly every game tick of the early learning phase. Thus, the agent has to explore large parts of the state-action space to improve its behavior, although the game could be easily won by applying a rough heuristic like always move right (> ) right [1:0]) for the first level. This renders the game an eligible test environment for our agent model.
We perform 100 runs for each level and measure the percentage of wins by the agent over 30 repetitions. Again, standard Q-Learning with and without the heuristics approach, as well as the heuristics-only approach are used, given the same standard parameters as provided in Section 5.2. Table 2 shows the results for the first and the third level of the game: With standard Q-Learning, the agent is not able to win the game within 100 runs, whereas using the heuristics approach, the agent wins both levels in over 50% of the cases. Surprisingly, the heuristics-only approach performs even better here. This seems to be the case since—although the game has some dynamics and can thus be considered more complex than the grid world scenarios—the considered levels allow for rougher heuristics than the grid worlds: In contrast to the grid worlds, the goal to be reached is not located in a single corner, instead, the game can be won by simply reaching the rightmost side of the screen (which can already be achieved by a very rough heuristic). In this paper, we described a model of a learning agent which is able to find and to exploit heuristics without a priori knowledge in unknown environments. We showed on several examples (four grid world scenarios and one game from the GVGAI framework) that our approach drastically accelerates the learning process to find optimal policies.
However, the approach is not perfect yet and leaves
room for future work: (1) The runtime to extract an HKB
should be further improved (a faster algorithm has been
proposed in
Furthermore, it could be interesting to extend the model with revision techniques for the found heuristics and to incorporate mechanisms to store and reuse heuristics.