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:
- 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.
- 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.
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).
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