Credit Assignment in Genetic Learning Systems

John J. GrefenstetteAAAI 1988

Overview

This paper introduces RUDI (Rule Discovery), a hybrid genetic learning system designed to solve the "credit assignment problem." By integrating rule-level performance metrics to physically cluster related rules before evolution, RUDI bridges the gap between historically competing approaches in genetic algorithms. Experimental results show that RUDI significantly outperforms systems relying solely on global fitness or individual rule strength.

The Credit Assignment Problem

In machine learning, the credit assignment problem involves determining which specific actions in a long sequence are responsible for an eventual outcome. For instance, in a multi-step task, the final action that triggers a reward is rarely the only one deserving of credit; preceding actions set the stage, but identifying their individual contributions is difficult.

Historically, researchers using Genetic Algorithms (GAs) for rule learning followed two paths:

  1. The Pittsburgh Approach (e.g., LS-1): Evolved entire rule sets as individuals. While effective for global optimization, it struggles to pinpoint which specific rules within a set are high-performing.
  2. The Michigan Approach (Classifier Systems): Evolved individual rules. This identifies useful rules but often fails to maintain the complex, multi-step sequences (chains) required for sophisticated tasks.
Figure 1: A fragment of the state space showing rule sequences (chains) leading to different rewards.

John Grefenstette identifies a critical gap: neither approach optimally handles the structural organization of rules needed to solve complex, multi-step tasks efficiently.

The RUDI Architecture

RUDI is a multilevel system that combines the strengths of both Pittsburgh and Michigan styles. Its primary innovations center on how rule "strength" is measured and utilized.

Dual Strength Metrics

RUDI maintains two distinct strength values for every rule:

  • PSP-Strength (Profit Sharing Plan): Estimates the expected external reward. This is used during problem-solving to select which rule to fire when multiple rules match the current state.
  • BBA-Strength (Bucket Brigade Algorithm): Tracks how rules fire in sequence. Rules that frequently trigger one another tend to converge toward similar BBA-strengths.

Heuristic Clustering and Structural Evolution

Before the Genetic Algorithm performs crossover (swapping rule segments between programs), RUDI sorts the rules within a program based on their BBA-Strength.

Figure 2: The heuristic clustering process, where rules are sorted by BBA-strength to preserve functional chains during crossover.

By sorting rules this way, those belonging to the same functional chain are physically grouped together. This increases the likelihood that a successful "building block" of rules will be inherited as a single unit by the next generation, rather than being disrupted by random crossover. This acts as an "intelligent inversion operator," solving linkage problems that random mutation typically cannot.

Experimental Evaluation

The system was tested on a synthetic Experimental State Space consisting of a cylindrical grid of 288 states. The task required navigating from one of 32 initial states to a final state in exactly eight steps using three possible moves (Left, Straight, or Right). The reward structure was non-linear, featuring "hills" of high reward separated by "valleys," necessitating the discovery of specific early-stage sequences to reach high-payoff zones.

Performance Analysis

RUDI was compared against several benchmarks, measuring average external reward over 1,000 test episodes:

System Ave. External Reward (Max 1000)
RUDI 943
LS-1.5 (PSP for action, no clustering) 791
LS-1.0 (Random action, no clustering) 724
PSP (Pure Classifier System) 632
BBA (Pure Classifier System) 468
Random Walk 250

RUDI significantly outperformed both the standard LS-1 and pure Classifier System variants. These results suggest that using BBA-strength for structural clustering—rather than just reward prediction—is a powerful meta-learning tool.

Conclusion and Future Directions

RUDI demonstrates that "strength" is context-dependent: one type is suited for action selection (PSP), while another is better for structural organization (BBA). By making the physical layout of rules reflect their functional relationships, RUDI accelerates the discovery of complex behaviors.

Future work may address current limitations, such as the difficulty the Bucket Brigade Algorithm faces with very long sequences without specialized "bridge" rules. Additionally, exploring how these credit assignment levels function in parallel systems—where multiple rules fire simultaneously—remains a promising area for research.

Summary updated

BibTeX
@inproceedings{grefenstette1988credit,
  author = {John J. Grefenstette},
  title = {{Credit Assignment in Genetic Learning Systems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
}
Figure