Alternatives for Classifier System Credit Assignment

1. Introduction

Credit assignment is the problem of determining how to reinforce individual rules in a multistep chain when the external reward is given only at the chain's con­ clusion. Some of the earliest work in credit assignment was Samuel's celebrated checker-playing program (1959 and 1967) which used a heuristic version of temporal difference (TD) methods (Sutton, 1988). These meth­ ods are similar in philosophy to the Adaptive Heuristic Critic (AHC) developed by Sutton (1984) and Barto, Sutton and Anderson (1983), the bucket brigade de­ veloped by Holland (1985 and 1986), and the learn­ ing systems studied by Witten (1977), Booker (1982), and Hampson (1983) . Each of these provides a mecha­ nism whereby adjustments to rule strength are made in an incremental fashion, in contrast to supervised learn­ ing with various backwards averaging schemes (Grefen­ stette, 1988; Widrow and Stearns, 1985; Holland and Reitman, 1978; and Rumelhart, Hinton and Williams, 1986).

Mark Palmer Gita Rangarajan

Energy Environment and Resources Center 10521 Research Drive, Suite 100 Knoxville, Tennessee 37932

This paper studies credit assignment in an environ­ ment with minimal prior knowledge. Initial investiga­ tion of three credit assignment methods has been under­ taken in terms of their speed and accuracy in learning abstract state-space maze problems. The three meth­ ods studied are the bucket brigade, backwards averag­ ing with classifier chunking, and a combination of the methods. The correspondence to TD and AHC meth­ ods is suggested.

1.1 Classifier Systems

Classifier systems to automatically discover rules to perform desired tasks were developed by Holland and Reitman (1978) and later refined by Holland (1986) . In contrast to traditional expert systems where rules are handcrafted by knowledge engineers, classifier sys­ tems use the genetic algorithm as a discovery operator to generate rules. Each classifier is an "if-then" rule , with a condition part and an action part. A message list is used to store the current environmental state and any internal messages. Associated to each classifier is a numerical value called its strength. Holland and Re­ itman (1978) adjusted classifier strength through back­ wards averaging and other central methods. The cur­ rent credit assignment standard is the bucket brigade (Holland, 1985) .

Should the conditional part of a classifier match a message(s) on the message list, the classifier pays a por­ tion of its strength (its bid) for the privilege of acting, whereupon the consequent action (which may be either an explicit action or the posting of an internal message) is taken. In the simplest classifier system implementa­ tion, the bid payment made by the acting classifier(s) is paid in equal proportions to classifiers acting in the previous cycle. Should competing classifiers specify in­ compatible actions, conflict resolution is based on the magnitude of the effective bids (determined as the sum of the bid plus a random variable chosen from a distri­ bution determined by a noise schedule). If the action results in an evaluation state, an appropriate reward or punishment is assigned to the acting classifiers of the current cycle. The "bid-payment" cycle is repeated for a predetermined number of cycles, whereupon the in­ dividual classifiers contribute to a gene pool in direct proportion to their strength and the genetic recombi­ nation operators are invoked.

Since Holland and Reitman's work, several vari­ ants of classifier systems have beeri successfully demon­ strated including solution of a difficult Boolean discov­ ery problem (Wilson, 1987a), discovery of an optimal pumping schedule and automatic leak detection for gas pipelines (Goldberg, 1983), and discovery of probabilis­ tic scheduling rules for job shop scheduling problems (Hilliard et. al., 1988). For additional descriptions of classifier system applications, the reader is referred to Davis, 1987; and Goldberg, 1989.

1.2 Problem Selection

The test bed of problems for this study were one, two, and three dimensional mazes with 64 possible states and with a specified start and goal. The chosen represen­ tation encoded the states as lattice points in Euclidean space. Allowable actions at any state were to make a single step move parallel to the coordinate axes (sub­ ject to the constraint that the move did not go outside the lattice). Upon attainment of the goal, the system was given a reward Rand was reset to the start.

Certain of the problems incorporated "barriers" at selected non-goal states. In one formulation, barrier states were all equally resistant to entry; in another, the barriers had relative "holes," states less resistant to entry. Barriers were not explicitly represented; in­ stead, classifiers responsible for system entry into bar­ rier states had their strength immediately decremented . This challenged the system to learn to associate cer­ tain states with punishment either through internally developed messages, mapping expected rewards onto states, or simply through the credit assignment mecha­ nism. The purpose of the barriers was to provide an ex­ perimental test to determine whether classifier systems could learn to pass through undesirable states (local minimums) to attain a global goal state (global maxi­ mums), and whether the systems could learn to distin­ guish between undesirable states of different intensities.

2. Credit Assignment

Although even genetic algorithm and stimulus-response classifier system performance is affected by the reward structure (Wilson, 1987a), reward and credit allocation issues become most apparent when rewards are delayed. Such a delay in reward causes difficulties for the ge­ netic algorithm (discovery) stage of the classifier sys­ tem, since its success depends on accurate estimates of the relative merit of the classifiers. Proper assessment of merit requires that the system frequently attain eval­ uation states and that the rewards and punishments be properly distributed to earlier stage setting classifiers. This must be accomplished rapidly without improperly restricting system exploration.

2.1 Earlier Studies

Credit assignment for "stage setting" classifiers has al­ ready been investigated by Wilson (1987b), Grefen­ stette (1988), and Riolo (1987,88). Wilson and Ri­ olo's studies have been limited, effectively, to non­ competitive chains of classifiers (Riolo had one pair of competing classifiers) and did not study credit assign­ ment in conjunction with genetic discovery. Results suggest that the number of steps necessary to reinforce a classifier in a chain (i.e., the number of cycles un­ til classifier-strength had attained a fixed proportion of steady state strength) is a linear function of the number of steps that the classifier is removed from the reward state.

Sometimes, even a linear function of the number of steps removed from the goal may be too slow for useful classifier chain development--Riolo's results sug­ gested that some 2100 cycles were required for attain­ ment of 90% of steady state for a classifier 12 steps removed from the goal. This potential difficulty has been recognized by Holland (1985) who conjectured that "bridging classifiers" would accelerate allocation of credit. Riolo (1987,88) has undertaken experiments that substantiate the potential usefulness of "bridging classifiers" once they have been discovered or manually injected. Unfortunately, the authors know of no case where "bridging classifiers" have been discovered by the system (our experiments have discovered rule sets in which certain classifiers act at more than one point in a rule chain and speed the distribution of credit, but they are not of the form Riolo suggests and their devel­ opment will depend on the chosen representation). To address the apparent failure of the bridging classifiers to spontaneously develop, Wilson (1987b) has formu­ lated the concept of hierarchical credit allocation, but that concept remains untested.

In contrast to Wilson and Riolo, Grefenstette (1988) was interested in predictive accuracy of learning and not learning speed. He compared RUDI, a vari­ ant of LS-1 (Smith, 1980), against the classifier system with the bucket brigade. He also provided experimental evidence that the bucket brigade leads to learning the next classifier's strength, whereas PSP (the profit shar­ ing plan -- backwards averaging with no attenuation) learns the expected system reward along the current subchain.

This study differs from previous work insofar as it addresses speed of learning of optimal solutions (short­ est paths start to goal; and in the case of barrier with hole, passing through the hole), both with fully enu­ merated conflicting rules and with discovery.

2.2 Desiderata and Techniques

Three heuristics motivate the credit assignment meth­ ods studied: 1. Reward the rules that have acted to form the chain from the start to the goal. 2. Draw the reward back from the goal to the start . 3. Break cycles.

Classifier reward is accomplished with three dif­ ferent mechanisms in this study: First, the conven­ tional bucket brigade. Second, a geometrically atten­ uated backwards averaging of the reward with classi­ fier chunking. Third, a combination of bucket brigade, backwards averaging, and classifier chunking. Back­ wards averaging is implemented through the mainte­ nance of a list of the classifiers that have fired since the last initialization of the task to the start. Once the reward is attained each classifier in the chain is re­ warded by the factor _xk, where the term .A, 0 < .A < 1, is the attenuation factor and k represents the number of steps between the last firing of the classifier and the attainment of the reward.

Classifier ch unking passes the full reward ( without attenuation) to all classifiers that have achieved a given percentage of steady state and link to the goal through

(minimum subpath) steady state classifiers. Any ad­ ditional attenuation is begun from this point. Cycle breaking (preventing "infinite loops" which do not pro­ duce useful actions) is accomplished by the assessment of an action tax. (This action tax has one additional benefit; it encourages the development of short chains.) These concepts are illustrated in Figure 1, where

S;(t) =strength of classifier i at updating t

BUCKET BRIGADE

some cycle, the current state matched the conditional part of no classifier in the population, the "cover de­ tector" mechanism (Robertson and Riolo, 1988) was invoked. The cover detector generates a classifier that matches the current state by copying the state into the classifier's conditional side, randomly flipping some of the bits to "don't cares" and randomly choosing the consequent action.

3.2 Parameter Settings

Each system was rewarded 500 units when it reached the goal, and was penalized -100 units if it suggested an action which would take it out of the maze (i .e. it bumped into the wall--a system that bumps into a wall does not change its environmental state, it is simply penalized). A penalty of -100 was associated to each cell of the barrier. The bucket brigade used a bid con­ stant of 0.1, that is, each rule that acts pays one tenth of its strength to the previously acting rule. An action tax of .01 was also assessed to discourage closed cycles and encourage shorter chains of rules. In contrast to the local payments of the bucket brigade, backwards averaging only occurs when the goal was reached. (The attenuation factor was 0.5. Moreover, each rule is re­ warded only once, according to its most recent firing in the chain--the recency heuristic, but not the frequency heuristic.) Other parameter settings were tried; these

3. Experiments

The environments chosen for the experiments reported here are 8 x 8 mazes. The mazes were used to verify the (sub) linearity of the bucket brigade credit allocation scheme as reported previously by Wilson (1987b) and Riolo (1987) and to compare the three credit allocation schemes -- unmodified bucket brigade, backwards av­ eraging with classifier chunking, and combination with classifier chunking.

3.1 Implementation

For every cycle of each maze, the classifier system is pro­ vided with the current state coordinates. The system matches these coordinates against the current popula­ tion of rules and, through a stochastic conflict resolu­ tion scheme based on rule strengths and noise schedule, determines the next action. The action is taken, and the system is moved to the new state. Since the state space is small (64 cells) in each of the mazes, all possible specific rules can be enumerated. If general rules (rules matching multiple states) are considered, then the size of the rule set becomes large under full enumeration and discovery becomes an important mechanism. In the discovery mode, the initial populations of classifiers were randomly chosen, and the genetic algorithm mod­ ified these populations as the search progressed. If at seemed to provide the best compromise between speed and finding an optimal solution.

Classifier chunking "chunked" the reward back through the maze as classifiers achieved 70% of steady state strength and linked to (minimal path) steady state subchains to the goal. Finally, the combination 'method used both the bucket brigade and backwards averaging.

4. Results

For the experiments with the bucket brigade and enu­ merated rules, steady state strengths were analytically calculated. In all other cases, a rule was assumed to be at steady state when the net gain or loss in strength throughout the traversal of the path was less than 5% of the current strength. In all cases, credit allocation was observed to be faster than a linear function of the dis­ tance to the goal as previously noted by Wilson(1987b) and Riolo (1987) in simpler experiments. (Although it might seem that according to the empirical definition of steady state a rule could achieve steady state at one cycle and lose it on another, that was never observed to happen.) It was also observed that 70% of steady state was a conservative measure of chain development; repeatable (sub) chains were observed to develop far earlier.

The remaining results are highly tentative. Full experimental designs weren't run; parameter settings weren't systematically studied, nor were all combina­ tions of methods investigated. A more systematic study will be undertaken.

4.1 Matrix Maze Problems-Enumerated Rules

Backwards averaging alone or in combination with the bucket brigade provides much faster feedback to the system than the bucket brigade alone. The barrier in­ variably slowed the learning for all the credit alloca­ tion mechanisms studied. (See Figure 2.) A potential drawback to more rapid credit assignment is the loss of exploration. With backwards averaging or the combi­ nation method, the system sometimes settled on a chain of rules longer than the minimal14 steps. Also, in some limited experiments with the barrier with hole, the bucket brigade found the hole while the backwards av­ eraging and combination runs tended to cross at higher penalties.

4.2 Matrix Maze Problems-Discovery

In comparison to the system with enumerated (specific) rules, convergence was much more rapid for the system with discovery of general rules. Presumably, the speed up is attributable to generalization and not to discovery, although follow-up experiments to confirm this hypoth­ esis have not been carried out. The ability to use a rule multiple times within a chain both shortens the effec­ tive length of the chain and provides earlier feedback to stage setting rules near the start . The bucket brigade can pass strength from a successor of a rule's instance late in the chain to the predecessor of the rule's instance early in the chain; therefore, the convergence curves are no longer monotonic. The pure backwards averaging method was not successful in finding minimal paths in the discovery environment, so that method is omitted from the results. Moreover, none of the methods was highly successful with the barrier with hole problem.

The bucket brigade credit assignment method en­ couraged sets of rules which navigated the maze effi­ ciently and avoided bumping into the walls, a serious problem for the combination method. Using the bucket brigade, a hierarchy developed in which rules specific to rows and columns adjacent to the walls dominated more general rules specifying movement down or to the right.

5. Relationship to Other Problems and Approaches

The credit assignment problem is of wide interest in all machine learning research that deals with delayed rewards, as for example, game playing. The approach developed here is closely related to Sutton's work lead­ ing to the Adaptive Heuristic Critic and the Method of Temporal Differences. In fact, the AHC approach currently is being incorporated into the classifier sys­ tem framework as an extension of this work (Brumgard, 1988) .

5.1 Adaptive Heuristic Critic (AHC)

The mechanism of the adaptive heuristic critic (AHC) can be directly incorporated into the classifier system and generates counterpart behavior to the heuristic credit allocation mechanisms explored in sections 3 and 4 of this paper. Let x[t] be a (dimension 64) vector rep­ resentation of the system state at timet; Xi ( t) = 1 if the system is in state i at timet, Xj(t) = 0 otherwise. Let c[t] be the indicator vector for classifier firing; ci(t) = 1 if classifier i fires at time t, and Cj ( t) = 0 otherwise. Let Sc[t] be the classifier strength vector at timet, and T a tax. R[t) represents the environmental reward (positive, negative, or zero) received at state t. The predicted reward p 8 [ t] represents the prediction (made while in state s) of the reward at state t, the heuristic reward r[t + 1) estimates the net gain (after the tax T) of mov­ ing from state t to state t + 1. The vector v[t] is the reward association vector at the time t and provides the current estimate of the expected reward at each of the states. Equation (5) defines the generic trace operator; the discounted average of past state visitations or clas­ sifier firings . The appropriate equations for the AHC formulation of the maze problems studied earlier in this paper are those for time-until-success tasks.

Commonalities with the previously described ap­ proach include the following: 1. The term "- T" in the heuristic reward plays the counterpart role to a tax in the classifier system. 2. The heuristic reward r[t + 1) estimates the net gain (after tax T) of moving from state t to t + 1. (The bucket brigade is the classifier counterpart to this, but for rules rather than states). 3. The strength update equation ( 4) affects a geomet­ rically attenuated backwards averaging of reward, both from the goal state, and from the heuristic rewards. (The classifier formulation in sections 3 and 4 did not use a full trace and did not incorporate an heuristic re­ ward into strength updates). 4. The reward association vector v[t] in effect "draws the reward back," somewhat analagously to classifier chunking.

There are important differences between the com­ bination method and the AHC. The AHC estimates expected reward at a state independent of classifier strengths, allowing the tradeoff between exploration and exploitation to be better controlled. Small values for the learning parameter encourage exploration; large values encourage exploitation (Sutton, 1989).

Another difference is that classifiers are loosely linked by equation (4) of the AHC formulation and strongly linked by the bucket brigade. Preliminary con­ siderations suggest that an AHC- bucket brigade com­ bination could provide a "second differences" effect that could help traverse local minima.

5.2 AHC Success

Brumgard (1988) reports success with limited experi­ ments using AHC with the square maze. He reports performance comparable to the combination method in all fully enumerated cases and the discovery barrier/no barrier cases. For the discovery barrier with hole case his AHC implementation was unable to find the hole. Sutton (1989) used AHC to solve a different (but sim­ ilar) planar maze problem with barrier and hole (with enumerated rules) wherein any suggested move into the barrier was reset to the previous state and the only ef­ fect on the AHC system (1H5) was the incurrence of the single-step tax "-T" and increment in time.

6. Conclusions

The incorporation of backwards averaging and classi­ fier chunking into the clas~ifier system seems to speed convergence; however, in the case of general rules (with discovery), this speed up may sacrifice exploration and generate less than optimal rule sets. Whether this is a property of general rule sets alone, or if discovery some­ how plays a role, is not known. Nor is it known if the various parameters could be tuned to overcome these difficulties. In contrast, the bucket brigade does demon­ strate the ability to assign credit in (sub) linear time, and seems to be especially competitive in the discovery setting with generalized rules and a barrier. Theoreti­ cal considerations and limited experiments suggest that adaptive heuristic critic holds promise for hybrid clas­ sifier systems. Finally, the acknowledgement is made that these represent a highly preliminary set of exper­ iments and much remains to be learned about credit assignment.

ACKNOWLEDGMENTS

The authors wish to thank Richard Sutton for many interesting and fruitful discussions.