Two Kinds of Training Information For Evaluation Function Learning

Paul E. Utgoff, Jeffrey A. ClouseAAAI 1991

Abstract

In the domain of heuristic search, the performance of an agent is heavily dependent on its evaluation function. Traditionally, these functions are trained using either Temporal Difference (TD) learning, which utilizes "vertical" information from search tree depth, or State Preference (SP) learning, which uses "horizontal" information from expert advice. This paper presents an integrated approach (I1) that combines these two sources of information. Experimental results on the Towers of Hanoi puzzle demonstrate that the integrated method learns faster, requires fewer expert queries, and overcomes the representational limitations that hinder pure TD learning.

Introduction

Heuristic search algorithms rely on evaluation functions to estimate the distance from a given state to a goal. Training these functions effectively is a central challenge in reinforcement learning. Two primary sources of training information exist:

  1. Temporal Difference (TD) Learning: This method propagates information "vertically" through the search tree. It adjusts the evaluation of a state based on the values of its successors, aiming to minimize the error between predicted and actual outcomes.
  2. State Preference (SP) Learning: This method utilizes "horizontal" information by comparing sibling states. An expert provides preferences (e.g., "state C is better than state B"), and the learner adjusts its function to reflect these relative rankings.

While TD learning is autonomous, it can be slow and sensitive to feature representation. SP learning is highly efficient but relies on expensive expert intervention. This paper proposes a hybrid model that leverages the strengths of both.

Methodology

The authors evaluate three distinct learning programs within a best-first search framework:

T1: The Temporal Difference Approach

T1 employs an absolute error correction rule. It adjusts weights so that the evaluation of a parent state aligns with the "backed-up" value of its most promising child. The goal is to learn the exact numerical distance to the goal state.

S1: The State Preference Approach

S1 treats expert-provided preferences as linear inequalities. If an expert selects state $C$ over $B$, the algorithm ensures $H(C) < H(B)$ (assuming lower values are better). Unlike T1, S1 focuses on the relative "slope" of the evaluation function rather than absolute values.

I1: The Integrated Approach

The novel I1 method uses TD learning as its baseline but incorporates a mechanism for expert consultation. It monitors its own TD error—the difference between its current estimate and the backed-up value. If this "surprise factor" exceeds a predefined threshold ($β$), the agent queries the expert for a preference. This allows the agent to be autonomous when confident and seek guidance when confused.

Experimental Setup

The methods were tested on the Towers of Hanoi puzzle with 3, 4, and 5 disks. This domain provides a clear state space where an optimal expert can be easily simulated. States are represented using Boolean features (e.g., "Is Disk 3 on Peg 3?"). For an $n$-disk problem, approximately $O(n^2)$ features are used.

Results and Analysis

The experimental results reveal significant differences in performance and robustness across the three methods.

Performance of TD (T1) and SP (S1) methods on the Towers of Hanoi puzzle.

As shown in the table above, the TD approach (T1) successfully solved the 3 and 4-disk problems but failed on the 5-disk problem, resulting in cyclic behavior ("cyc"). This failure stems from the fact that the exact distances to the goal were not linearly representable within the chosen feature space. In contrast, the SP approach (S1) solved all versions optimally ("opt") in very few trials, confirming that learning relative rankings is often a simpler task than learning absolute values. However, S1 required a significant number of expert queries (up to 31 for 5 disks).

Performance of the Integrated (I1) approach on the Towers of Hanoi puzzle.

The Integrated approach (I1) outperformed both baseline methods. It solved all problem sizes optimally. Notably, for the 4-disk problem, I1 achieved optimal performance in a single trial, requiring fewer weight adjustments than T1 and fewer expert queries than S1. By using the expert to "kickstart" learning and TD to refine it, I1 balances efficiency with autonomy.

Conclusion

This research demonstrates that "vertical" and "horizontal" training signals are complementary rather than redundant. The integrated I1 model effectively uses expert advice to navigate complex feature spaces where pure TD learning fails, while using TD learning to reduce the long-term dependency on the expert. Future work will explore the robustness of this integration in the presence of fallible experts and its scalability to more complex domains like Air Traffic Control.

Summary updated

BibTeX
@inproceedings{utgoff1991two,
  author = {Paul E. Utgoff and Jeffrey A. Clouse},
  title = {{Two Kinds of Training Information For Evaluation Function Learning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1991},
}
Figure