1.1 OVERGENERAL AND STRONG OVERGENERAL RULES

Dealing with overgeneral rules – rules which are simply too general – is a fundamental problem for LCS. Such rules may specify the desired action in a subset of the states they match, but, by definition, not in all states, so relying on them harms performance.

Another problem faced by some LCS is greedy classifier creation (Cliff and Ross, 1995; Wilson, 1994). To obtain better rules, an LCS’s GA allocates reproductive events preferentially to rules with higher fitness. Greedy classifier creation occurs in LCS in which the fitness of a rule depends on the magnitude of the reward it receives from the problem environment. In such systems rules which match in higher-rewarding parts of the environment will reproduce more than others. If the bias in reproduction of rules is strong enough there may be too few rules, or even no rules, matching low-rewarding states. (In the latter case, we say there’s a gap in the rules’ covering map of the input/action space.)

Cliff and Ross (1995) recognised that overgeneral rules can interact with greedy classifier creation, an effect Kovacs (2000) referred to as the problem of strong overgenerals. The interaction occurs when an overgeneral rule acts correctly in a high reward state and incorrectly in a low reward state. The rule is overgeneral because it acts incorrectly in one state, but at the same time it prospers because of greedy classifier creation and the high reward it receives in the other state. The proliferation of strong overgenerals can be disastrous for the performance of an LCS: such rules are unreliable, but outweigh more reliable rules when it comes to action selection. Worse, they may prosper under the influence of the GA, and may even reproduce more than reliable but low-rewarding rules, possibly driving them out of the population.

This work extends the analysis of strong overgenerals in (Kovacs, 2000) to show exactly what requirements must be met for them to arise in both strength and accuracy-based LCS. In order to compare the two approaches we begin by defining Goliath, a strength-based LCS which differs as little as possible from accuracy-based XCS, which allows us to isolate the effects of the fitness calculation on performance. We then argue that different definitions of overgenerality and strong overgenerality are appropriate for the two types of LCS. We later make a further, novel, distinction between strong and fit overgeneral rules. We present minimal environments which will support strong overgenerals, demonstrate the dependence of strong overgenerals on the reward function, and prove certain theorems regarding their prevalence under simplifying assumptions. We show that strength and accuracy-based fitness have different kinds of tolerance for biases (see section 3.5) in reward functions, and (within the context of various simplifying assumptions) to what extent we can bias them without producing strong overgenerals. We show what kinds of problems will not produce strong overgenerals even without our simplifying assumptions. We present results of experiments which show how XCS and Goliath differ in their response to fit overgenerals. Finally, we consider the value of the approach taken here and directions for further study.

Reinforcement learning consists of cycles in which a learning agent is presented with an input describing the current environmental state, responds with an action and receives some reward as an indication of the value of its action. The reward received is defined by the reward function, which maps state/action pairs to the real number line, and which is part of the problem definition (Sutton and Barto, 1998). For simplicity we consider only single-step tasks, meaning the agent’s actions do not affect which states it visits in the future. The goal of the agent is to maximise the rewards it receives, and, in single-step tasks, it can do so in each state independently. In other words, it need not consider sequences of actions in order to maximise reward.

When an LCS receives an input it forms the match set [M] of rules whose conditions match the environmental input.¹ The LCS then selects an action from among those advocated by the rules in [M]. The subset of [M] which advocates the selected action is called the action set [A]. Occasionally the LCS will trigger a reproductive event, in which it calls upon the GA to modify the population of rules.

We will consider LCS in which, on each cycle, only the rules in [A] are updated based on the reward received - rules not in [A] are not updated.

2.2 THE STANDARD TERNARY LCS LANGUAGE

A number of representations have been used with LCS, in particular a number of variations based on binary and ternary strings. Using what we’ll call the standard ternary LCS language each rule has a single condition and a single action. Conditions are fixed length strings from {0, 1, #}^l, while rule actions and environmental inputs are fixed length strings from {0,1}^l. In all problems considered here l = 1.

A rule’s condition c matches an environmental input m if for each character m_i the character in the corresponding position c_i is identical or the wildcard (#). The wildcard is the means by which rules generalise over environmental states; the more #s a rule contains the more general it is. Since actions do not contain wildcards the system cannot generalise over them.

2.3 STRENGTH-BASED AND ACCURACY-BASED FITNESS

Although the fitness of a rule is determined by the rewards the LCS receives when it is used, LCS differ in how they calculate rule fitness. In traditional strength-based systems (see, e.g., Goldberg, 1989; Wilson, 1994), the fitness of a rule is called its strength. This value is used in both action selection and reproduction. In contrast, the more recent accuracy-based XCS (Wilson, 1995) maintains separate estimates of rule utility for action selection and reproduction.

One of the goals of this work is to compare the way strength and accuracy-based systems handle overgeneral and strong overgeneral rules. To do so, we'll compare accuracy-based XCS with a strength-based LCS called Goliath which differs as little as possible from XCS, and which closely resembles Wilson's ZCS (Wilson, 1994). To be more specific, Goliath (in single-step tasks) uses the delta rule to update rule strengths:

Strength (a.k.a. prediction):

sj←sj+β(R−sj)$s_j\leftarrow s_j+\mathrm{\beta }\left(R-s_j\right)$

where s_j is the strength of rule j, 0 < β ≤ 1 is a constant controlling the learning rate and R is the reward from the environment. Goliath uses the same strength value for both action selection and reproduction. That is, the fitness of a rule in the GA is simply its strength.

XCS uses this same update to calculate rule strength,² and uses strength in action selection, but goes on to derive other statistics from it. In particular, from strength it derives the accuracy of a rule, which it uses as the basis of its fitness in the GA. This is achieved by updating a number of parameters as follows (see Wilson, 1995, for more). Following the update of a rule’s strength s_j, we update its prediction error ε_j:

Prediction error:

${\mathrm{\epsilon }}_j\leftarrow {\mathrm{\epsilon }}_j+\mathrm{\beta }\left(\frac{\left|R-s_j\right|}{R_{\text{max}}-R_{\text{min}}}-{\mathrm{\epsilon }}_j\right)$

where R_max and R_min are the highest and lowest rewards possible in any state. Next we calculate the rule’s accuracy icy:

Accuracy:

${\mathrm{k}}_j=\left\{\begin{array}{cc}\hfill 1\hfill & \hfill \mathrm{if}{\mathrm{\epsilon }}_j<{\mathrm{\epsilon }}_o\hfill \\ \hfill \alpha {\left({\mathrm{\epsilon }}_j/{\mathrm{\epsilon }}_o\right)}^{-v}\hfill & \hfill \mathrm{otherwise}\hfill \end{array}\right.$

where 0 < ε_o is a constant controlling the tolerance for prediction error and 0 < α < 1 and 0 < v are constants controlling the rate of decline in accuracy when ε_o is exceeded. Once the accuracy of all rules in [A] has been updated we update each rule’s relative accuracy K_j^@ #:

Relative accuracy:

$K_j^{@\#}\leftarrow \frac{K_j}{{\displaystyle \sum _{x\in \left[A\right]}{K}_x}}$

Finally, each rule’s fitness is updated:

Fitness:

$F_j\leftarrow F_j+\mathrm{\beta }\left(K_j^{@\#}-F_j\right)$

To summarise, the XCS updates treat the strength of a rule as a prediction of the reward to be received, and maintain an estimate of the error ε_j in each rule’s prediction. An accuracy score K_j is calculated based on the error as follows. If error is below some threshold ε_o the rule is fully accurate (has an accuracy of 1), otherwise its accuracy drops off quickly. The accuracy values in the action set [A] are then converted to relative accuracies (the k_j' update), and finally each rule’s fitness F_j is updated towards its relative accuracy.

To simplify, in XCS fitness is an inverse function of the error in reward prediction, with errors below ε_o being ignored entirely.

2.4 METHOD

LCS are complicated systems and analysis of their behaviour is often quite difficult. To make our analysis more tractable we’ll make a number of simplifications, perhaps the greatest of which is to study very small problems. Although very small, these problems illustrate different types of rules and the effects of different fitness definitions on them – indeed, they illustrate them better for their simplicity.

Another great simplification is to consider the much simpler case of single-step problems rather than multi-step ones. Multi-step problems present their own difficulties, but those present in the single-step case persist in the more complex multi-step case. We feel study of single-step problems can uncover fundamental features of the systems under consideration while limiting the complexity which needs to be dealt with.

To further simplify matters we’ll remove the GA from the picture and enumerate all possible classifiers for each problem, which is trivial given the small problems we’ll consider. Simplifying further still, we’ll consider only the expected values of rules, and not deviations from expectation. Similarly, we’ll consider steady state values, and not worry about how steady state values are reached (at least not until section 7). We’ll consider deterministic reward functions, although it would be easy to generalise to stochastic reward functions simply by referring to expected values. We’ll restrict our considerations to the standard ternary LCS language of section 2.2 because it is the most commonly used and because we are interested in fitness calculations and the ontology of rules, not in their representation. Finally, to simplify our calculations we’ll assume that, in all problem environments, states and actions are chosen equiprobably.

Removing the GA and choosing actions at random does not leave us with much of a classifier system. In fact, our simplifications mean that any quantitative results we obtain do not apply to any realistic applications of an LCS. Our results will, however, give us a qualitative sense of the behaviour of two types of LCS. In particular, this approach seems well suited to the qualitative study of rule ontology. Section 3 contains examples of this approach.

Since the goal of our reinforcement learning agents is to maximise the rewards they receive, it’s useful to have terminology which distinguishes actions which do so from those which do not:

Correct action: In any given state the learner must choose from a set of available actions. A correct action is one which results in the maximum reward possible for the given state and set of available actions.

Incorrect action: One which does not maximise reward.

Table 1 defines a simple single-step test problem, in which for state 0 the correct action is 0, while in state 1 both actions 0 and 1 are correct. Note that an action is correct or incorrect only in the context of a given state, and the context of the rewards available in that state.

3.2 OVERGENERAL RULES

Table 2 shows all possible rules for the environment in table 1 using the standard ternary language of section 2.3. Each rule’s expected strength is also shown, using the simplifying assumption of equiprobable states and actions from section 2.4. The classification shown for each rule will eventually be explained in sections 3.2.2 and 3.2.3.

We’re interested in distinguishing overgeneral from non-overgeneral rules. Rules A,B,C and D are clearly not overgeneral, since they each match only one input. What about E and F? So far we haven’t explicitly defined overgenerality, so let’s make our implicit notion of overgenerality clear:

Overgeneral rule: A rule O from which a superior rule can be derived by reducing the generality of O’s condition.

This definition seems clear, but relies on our ability to evaluate the superiority of rules. That is, to know whether a rule X is overgeneral, we need to know whether there is any possible Y, some more specific version of X, which is superior to X. How should we define superiority?

3.3 STRONG OVERGENERAL RULES

Now that we’ve finally defined overgenerality satisfactorily let’s turn to the subject of strong overgenerality. Strength is used to determine a rule’s influence in action selection, and action selection is a competition between alternatives. Consequently it makes no sense to speak of the strength of a rule in isolation. Put another way, strength is a way of ordering rules. With a single rule there are no alternative orderings, and hence no need for strength.

In other words, strength is a relation between rules; a rule can only be stronger or weaker than other rules – there is no such thing as a rule which is strong in isolation. Therefore, for a rule to be a strong overgeneral, it must be stronger than another rule. In particular, a rule’s strength is relevant when compared to another rule with which it competes for action selection.

Now we can define strong overgeneral rules, although to do so we need two definitions to match our two definitions of overgenerality:

Strength-based strong overgeneral: A rule which sometimes advocates an incorrect action, and yet whose expected strength is greater than that of some correct (i.e. not-overgeneral) competitor for action selection.

Accuracy-based strong overgeneral: A rule whose strength oscillates unacceptably, and yet whose expected strength is greater than that of some accurate (i.e. not-overgeneral) competitor for action selection.

The intention is that competitors be possible, not that they need actually exist in a given population.

The strength-based definition refers to competition with correct rules because strength-based systems are not interested in maintaining incorrect rules (see section 3.2.2). This definition suits the analysis in this work. However, situations in which more overgeneral rules have higher fitness than less overgeneral – but still overgeneral – competitors are also pathological. Parallel scenarios exist for accuracy-based fitness. Such cases resemble the well-known idea of deception in GAs, in which search is lead away from desired solutions (see, e.g., Goldberg, 1989).

3.4 FIT OVERGENERAL RULES

In our definitions of strong overgenerals we refer to competition for action selection, but rules also compete for reproduction. To deal with the latter case we introduce the concept of fit overgerterals as a parallel to that of strong overgenerals. A rule can be both, or either. The definitions for strength and accuracy-based fit overgenerals are identical to those for strong overgenerals, except that we refer to fitness (not expected strength) and competition for reproduction (not action selection):

Strength-based fit overgeneral: A rule which sometimes advocates an incorrect action, and yet whose expected fitness is greater than that of some correct (i.e. not-overgeneral) competitor for reproduction.

Accuracy-based fit overgeneral: A rule whose strength oscillates unacceptably, and yet whose expected fitness is greater than that of some accurate (i.e. not-overgeneral) competitor for reproduction.

We won’t consider fit overgenerals as a separate case in our initial analysis since in Goliath any fit overgeneral is also a strong overgeneral.⁵ Later, in section 7, we’ll see how XCS handles both fit and strong overgenerals.

3.5 OTHER DEFINITIONS

For reference we include a number of other definitions:

Reward function: A function which maps state/action pairs to a numeric reward.

Constant function: A function which returns the same value regardless of its arguments. A function may be said to be constant over a range of arguments.

Unbiased reward function: One in which all correct actions receive the same reward.

Biased reward function: One which is not unbiased.

Best action only map: A population of rules which advocates only the correct action for each state.

Complete map: A population of rules such that each action in each state is advocated by at least one rule.

4.1 THE REWARD FUNCTION IS RELEVANT

Let’s look at the last two requirements for strong overgenerals in more detail. First, in order to have differences in the expectations of the strengths of rules there must be differences in the rewards returned from the environment. So the values in the reward function are relevant to the formation of strong overgenerals. More specifically, it must be the rewards returned to competing classifiers which differ. So subsets of the reward function are relevant to the formation of individual strong or fit overgenerals.

In (Kovacs, 2000), having different rewards for different correct actions is called a bias in the reward function (see section 3.5). For strong or fit overgenerals to occur, there must be a bias in the reward function at state/action pairs which map to competing classifiers.

5.1 A 2x2 ENVIRONMENT

We’ve just seen an example where any bias in the reward function will produce strong overgenerals. However, this is not the case when we have more than one action available, as in table 4. The strengths of the two fully generalised rules, E & F, are dependent only on the values associated with the actions they advocate. Differences in the rewards returned for different actions do not result in strong overgenerals – as long as we don’t generalise over actions, which was one of our assumptions from section 2.4.

5.2 SOME PROPERTIES OF ACCURACY-BASED FITNESS

At this point it seems natural to ask how common strong overgenerals are and, given that the structure of the reward function is related to their occurrence, to ask what reward functions make them impossible. In this section we’ll prove some simple, but perhaps surprising, theorems concerning overgeneral rules and accuracy-based fitness. However, we won’t go too deeply into the subject for reasons which will become clear later.

Let’s begin with a first approximation to when overgeneral rules are impossible:

More generally, strong overgenerals are impossible when the reward function is sufficiently close to constancy over each action that oscillations in any rule's strength are less than τ. Now we can see when strong overgenerals are possible:

In other words, if the rewards for the same action differ by more than τ the fully generalised rule for that action will be overgeneral. To avoid overgeneral rules completely, we’d have to constrain the reward function to be within i of constancy for each action. That overgeneral rules are widely possible should not be surprising. But it turns out that with accuracy-based fitness there is no distinction between overgeneral and strong overgeneral rules:

Taking theorems 2 and 3 together yields:

In short, using accuracy-based fitness and reasonably small x only a highly restricted class of reward functions and environments do not support strong overgeneral rules. These theorems hold for environments with more than 2 actions.

Note that the ‘for each action’ part of the theorems we’ve just seen depends on the inability of rules to generalise over actions, a syntactic limitation of the standard LCS language. If we remove this arbitrary limitation then we further restrict the class of reward functions which will not support strong overgenerals.

6.1 WHEN ARE STRONG OVERGENERALS IMPOSSIBLE IN A STRENGTH LCS?

Let’s begin with a first approximation to when strong overgenerals are impossible:

To make theorem 5 more concrete, reconsider the reward values in table 4. By definition, a correct action in a state is one which returns the highest reward for that state, so if we want w and z to be the only correct actions then w > y,z > x. If the reward function returns the same value for all correct actions then w = z. Then the strengths of the overgeneral rules are less than those of the correct accurate rules: E’s expected strength is (w + x)/2 which is less than A’s expected strength of wand F’s expected strength is (y + z)/2 which is less than D’s z, so the overgenerals cannot be strong overgenerals. (If w < y and z < x then we have a symmetrical situation in which the correct action is different, but strong overgenerals are still impossible.)

6.2 WHAT MAKES STRONG OVERGENERALS POSSIBLE IN STRENGTH LCS?

It is possible to obtain strong overgenerals in a strength-based system by defining a reward function which returns different values for correct actions. An example of a minimal strong overgeneral supporting environment for Goliath is given in table 6. Using this reward function, E is a strong overgeneral, as it is stronger than the correct rule D with which it competes for action selection (and for reproduction if the GA runs in the match set or panmictically (see Wilson, 1995)).

However, not all differences in rewards are sufficient to produce strong overgenerals. How much tolerance does Goliath have before biases in the reward function produce strong overgenerals? Suppose the rewards are such that w and z are correct (i.e. w > y,z > x) and the reward function is biased such that w > z. How much of a bias is needed to produce a strong overgeneral? I.e. how much greater than z must w be? Rule E competes with D for action selection, and will be a strong overgeneral if its expected strength exceeds D’s, i.e. if (w + x)/2 > z, which is equivalent to w > 2z – x. So a bias of w > 2z – x means E will be a strong overgeneral with respect to D, while a lesser bias means it will not.

E also competes with A for reproduction, and will be fitter than A if (w + x)/2 > w, which is equivalent to x > w. So a bias of x > w means E will be a fit overgeneral with respect to A, while a lesser bias means it will not. (Symmetrical competitions occur between F & A and F & D.)

We’ll take the last two examples as proof of the following theorem:

The examples in this section show there is a certain tolerance for differences in rewards within which overgenerals are not strong enough to outcompete correct rules. Knowing what tolerance there is is important as it allows us to design single-step reward functions which will not produce strong overgenerals. Unfortunately, because of the simplifying assumptions we’ve made (see section 2.4) these results do not apply to more realistic problems. However, they do tell us how biases in the reward function affect the formation of strong overgenerals, and give us a sense of the magnitudes involved. An extension of this work would be to find limits to tolerable reward function bias empirically. Two results which do transfer to more realistic cases are theorems 1 and 5, which tell us under what conditions strong overgenerals are impossible for the two types of LCS. These results hold even when our simplifying assumptions do not.

8.1 EXTENSIONS AND QUANTITATIVE ANALYSIS

We could extend the approach taken in this work by removing some of the simplifying assumptions we made in section 2.4 and dealing with the resultant additional complexity. For example, we could put aside the assumption of equiprobable states and actions, and extend the inequalities showing the requirements of the reward function for the emergence of strong overgenerals to include the frequencies with which states and actions occur. Taken far enough such extensions might allow quantitative analysis of non-trivial problems. Unfortunately, while some extensions would be fairly simple, others would be rather more difficult.

At the same time, we feel the most significant results from this approach are qualitative, and some such results have already been obtained: we have refined the concept of overgenerality (section 3.2), argued that strength and accuracy-based LCS have different goals (section 3.2), and introduced the concept of fit overgenerals (section 3.4).

We’ve seen that, qualitatively, strong and fit overgenerals depend essentially on the reward function, and that they are very common. We’ve also seen that the newer accuracy-based fitness has, so far, dealt with them much better than Goliath’s more traditional strength-based fitness (although we have not yet considered default hierarchies). This is in keeping with the analysis in section 3.2.1 which suggests that using strength as fitness results in a mismatch between the goals of the LCS and its GA.

Rather than pursue quantitative results we would prefer to extend this qualitative approach to consider the effects of default hierarchies and mechanisms to promote them, and the question of whether persistent strong and fit overgenerals can be produced under accuracy-based fitness. Also of interest are multi-step problems and hybrid strength/accuracy-based fitness schemes, as opposed to the purely strength-based fitness of Goliath and purely accuracy-based fitness of XCS.