Reinforcement Learning with a Hierarchy of Abstract Models

Satinder P. SinghAAAI 1992

Introduction

In the early 1990s, Reinforcement Learning (RL) faced a significant "scaling wall." Standard algorithms, such as Temporal Difference (TD) learning, operated exclusively at the level of primitive actions—the smallest possible units of movement. In large or complex environments, the number of updates (backups) required for reward information to propagate back to the starting state was prohibitively high. Satinder Singh's 1992 paper introduced H-DYNA, a foundational architecture in Hierarchical Reinforcement Learning (HRL) designed to overcome this by enabling agents to learn and plan using a hierarchy of models that abstract away temporal details.

The H-DYNA Architecture

H-DYNA extends Richard Sutton’s original DYNA architecture. While DYNA learns a model of the world to perform "simulated experience" updates, H-DYNA introduces a multi-level hierarchy:

  • Hierarchy of Models: The system maintains multiple environment models. Level 1 (M-1) represents standard primitive actions. Level 2 (M-2) treats entire sub-tasks (e.g., "visit Point A") as single "abstract actions."
  • Abstract Payoffs and Costs: Instead of just predicting the next state, the agent learns the expected cumulative reward and the temporal cost (time/effort) associated with performing a sub-task.
  • Closed-Loop Abstract Actions: Unlike rigid macro-sequences, these abstract actions are closed-loop policies defined by goal states, allowing them to remain robust in stochastic environments.
  • Simulated Planning: During "downtime," the agent performs backups within these abstract models. A single update in a high-level model like M-2 can be equivalent to dozens or hundreds of updates in the primitive M-1 model.

Experimental Setup

The architecture was evaluated using a custom 8x8 Grid World simulation. The environment contains obstacles and three specific landmark locations: A, B, and C.

The 8x8 Grid World environment featuring landmarks A, B, and C used for evaluating H-DYNA.

The agent was trained on "elemental tasks" (e.g., "Go to A") and "composite tasks" (e.g., "Go to A, then B, then C"). The primary benchmark was the number of backups required for the value function to converge to an optimal policy, comparing H-DYNA against traditional "flat" RL (using only the M-1 model).

Key Results and Insights

The core finding of the paper is the dramatic efficiency gain provided by abstract backups. Because an abstract action spans multiple time steps, updating its value propagates information across the state space much faster than primitive updates.

Comparison of convergence rates between the primitive model (M-1) and the abstract model (M-2), showing a significant reduction in required backups for the latter.

As shown in the results, the value function for a complex composite task converged to near-optimal levels in approximately 5,000 backups using the abstract model (M-2). In stark contrast, the primitive model (M-1) required over 150,000 backups to achieve comparable accuracy. Furthermore, by learning models for elemental tasks, the agent builds a library of skills that can be transferred to new composite tasks, rather than learning from scratch.

Limitations and Future Directions

While H-DYNA demonstrates the power of temporal abstraction, it relies on pre-defined sub-goals (visiting A, B, or C). A truly autonomous system would need the capability to discover these "landmark states" or "interesting events" without human intervention. Additionally, while H-DYNA improves planning speed, the computational cost of building and maintaining multiple abstract models must be balanced against the complexity of the task. Future work in this area points toward structural abstraction—grouping similar states together—to further enhance scalability in even larger environments.

Summary updated

BibTeX
@inproceedings{singh1992reinforcement,
  author = {Satinder P. Singh},
  title = {{Reinforcement Learning with a Hierarchy of Abstract Models}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1992},
}
Figure