Lazy ExplanationBased Learning: A Solution to the Intractable Theory Problem

Prasad Tadepalli

Introduction

Explanation-Based Learning (EBL) emerged in the 1980s as a powerful paradigm for knowledge acquisition. By leveraging a "domain theory"—a set of rules governing a specific environment—an EBL system can analyze a single training example, construct an explanation for its success, and generalize this into a reusable plan. However, traditional EBL faces a significant hurdle in complex, "combinatorially explosive" domains like chess: the Intractable Theory Problem. In such domains, providing a complete proof for why a move is optimal requires an exhaustive search of all possible counter-moves, a process that can be more computationally expensive than the original problem-solving task.

The LEBL Architecture

To address this, Prasad Tadepalli introduced Lazy EBL (LEBL). Rather than seeking perfect, exhaustive proofs, LEBL adopts a "good enough" approach, learning from incomplete explanations and refining them incrementally.

The LEBL system architecture showing the interaction between the Teacher, Learner, and Planner.

As shown in Figure 1, the system consists of three primary components:

  1. Teacher: Provides examples, problems, and criticisms.
  2. Learner: Generates O-plans (Optimistic Plans) based on domain theory and teacher input.
  3. Planner: Executes these plans to solve problems, feeding solutions back to the teacher and signaling failures to the learner.

Methodology: Learning from Incompleteness

The core of LEBL is the Omniscience Assumption: the system assumes that the only relevant moves are those it already knows through its current library of plans. This drastically prunes the search space during the explanation phase.

Key mechanisms include:

  • O-plans: Sequences of moves that achieve a goal under the assumption that the opponent will not interfere in ways the system hasn't yet encountered.
  • Incremental Refinement: When an O-plan fails due to an unforeseen counter-move, the system doesn't discard it. Instead, it explains the failure, learns a counter-plan, and links it to the original plan to increase robustness.
  • Plan Combinators: Simple plans are merged into complex "c-plans" using operators like SEQ (sequence) and MESH (interleaving).

Experimental Evaluation

The system was evaluated using King and Pawn endgames in chess, a domain characterized by deep search trees. The domain theory utilized standard chess rules defined as STRIPS-style operators. LEBL was trained on 19 examples and tested on 8 novel problems.

Its performance was compared against the Alpha-Beta Explainer (ABE), a traditional EBL system that performs full searches to find complete explanations.

Comparison of search nodes explored by ABE vs. LEBL across 19 training examples.

Results and Discussion

The results, summarized in Figure 4, demonstrate that LEBL consistently outperforms ABE in search efficiency. In many instances where ABE required searching over 50,000 nodes, LEBL achieved the same learning goal in under 100 nodes—representing an improvement of two to three orders of magnitude.

Furthermore, LEBL showed significant accuracy gains. On the test set, errors in the first move dropped from 8 (with no prior knowledge) to just 2 after training. Interestingly, the search effort often decreased as the system matured, as learned O-plans allowed the planner to bypass expensive combinatorial searches.

Conclusion and Future Work

Lazy EBL demonstrates that in complex domains, it is often computationally cheaper to be "optimistically wrong" and fix errors later than to be "perfectly right" initially. This mimics human learning, which often relies on default assumptions and incremental refinement.

Future research must address the Utility Problem: as the library of O-plans grows, the cost of matching plans to the current state increases. Additionally, scaling LEBL to full-scale chess or other strategic domains remains a primary challenge for the field.

Summary updated

Abstract

Explanation-Based Learning (EBL) depends on the ability of a system to explain to itself, based on the domain theory, that a given training example is a member of the target concept. However, in many complex domains it is often intractable to do this. In this paper I introduce a learning technique called Lazy Explanation-Based Learning as a solution to the problem of intractable explanation process in EBL. This technique is based on the idea that when the domain theory is intractable, it is possible to learn by generalizing incomplete explanations and incrementally refining the over-general knowledge thus learned when met with unexpected plan failures. I describe a program that incrementally learns planning knowledge in game domains through Lazy Explanation-Based Learning. I present both empirical and theoretical evidence for the viability of Lazy Explanation-Based Learning.
BibTeX
@inproceedings{tadepalli1989lazy,
  author = {Prasad Tadepalli},
  title = {{Lazy ExplanationBased Learning: A Solution to the Intractable Theory Problem}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1989},
  url = {https://openreview.net/forum?id=SkZK3VGObr},
}
Figure