Reinforcement Learning with Hierarchies of Machines

Ronald Parr, Stuart J. RussellNeurIPS 1997 · OpenReview

This foundational 1998 paper by Ronald Parr and Stuart Russell introduces a framework for hierarchical reinforcement learning (HRL). By injecting prior knowledge into an agent through a hierarchy of state machines, the authors demonstrate how to significantly restrict possible behaviors, leading to orders-of-magnitude speedups in complex environments compared to standard "flat" reinforcement learning.

The Curse of Dimensionality in RL

Reinforcement learning (RL) is notoriously difficult to scale. In large environments, an agent often spends an eternity in a "blind search" phase, executing random actions that rarely lead to a reward. Standard RL agents typically treat every state-action pair as equally novel, forcing them to learn everything from scratch.

Humans, on the other hand, use high-level concepts (like "walk to the door") rather than thinking about individual muscle contractions. The challenge addressed in this paper is how to formally provide an agent with high-level "sketches" of a solution while still allowing it to learn the optimal way to fill in the details.

Hierarchical Abstract Machines (HAMs)

The core innovation of this work is the Hierarchical Abstract Machine (HAM). A HAM acts as a nondeterministic finite-state controller that can call other controllers as subroutines, effectively constraining the search space of the RL agent.

A HAM consists of four types of states:

  1. Action states: Execute a primitive action in the environment (e.g., "move north").
  2. Call states: Invoke another HAM as a subroutine.
  3. Choice states: Nondeterministically choose the next machine state. This is where the learning happens.
  4. Stop states: Halt the current machine and return control to the caller.

When a HAM is combined with a Markov Decision Process (MDP), the resulting system becomes a Semi-Markov Decision Process (SMDP). Because the HAM constrains the agent's choices, this "induced" SMDP is much smaller than the original MDP. The authors introduce HAMQ-learning, a variant of Q-learning that only updates values at the HAM's choice points. This allows the agent to ignore the "boring" parts of the state space where it is simply following a pre-defined script.

Experimental Validation

The authors evaluated their approach on a custom grid-world navigation task consisting of approximately 3,600 states. The environment featured a complex layout with hallways and obstacles, alongside stochastic movement dynamics where actions only succeeded 80% of the time.

Grid-world environment and HAM state machine

To navigate this maze, the researchers designed a three-level HAM hierarchy. The top level chooses a general direction of travel, the middle level handles hallway navigation, and the bottom level contains specific strategies for navigating around obstacles (e.g., choosing between "follow the wall" or "back off").

Key Results

The experimental results demonstrated a massive performance gap between HAM-based learning and standard "flat" RL:

  • Computational Speedup: Using policy iteration, the HAM approach found a good policy in just 185 seconds, compared to 4,544 seconds for the standard approach—a 24x speedup.
  • Sample Efficiency: HAMQ-learning required only 270,000 iterations to reach a performance level that standard Q-learning couldn't achieve even after 9,000,000 iterations.
  • Asymptotic Performance: Even after 20 million iterations, the flat Q-learning agent failed to match the performance of the HAM-constrained agent. The prior knowledge embedded in the HAM successfully prevented the agent from getting "lost" in the massive state space.

Insights and Limitations

This paper highlights that in RL, constraints can be a powerful feature. By telling the agent what not to do, it finds what it should do much faster. Furthermore, because the agent only learns at "choice points," the problem complexity drops from exponential to something much closer to linear in the number of actual decisions. Unlike many heuristic hierarchical methods, HAMs also provide strict formal guarantees, ensuring the solution found is provably optimal within the class of policies allowed by the HAM.

However, the approach is not without limitations. The primary bottleneck is the burden of design: a human must carefully engineer the HAM. If the HAM is poorly designed and excludes the truly optimal path, the agent will never find it. Additionally, the paper assumes a fully observable environment, and applying HAMs to partially observable environments (POMDPs) remains significantly more complex. Future work in this domain points toward "inductive learning" to automatically discover these hierarchies from experience.

Summary updated

Abstract

We present a new approach to reinforcement learning in which the poli(cid:173) cies considered by the learning process are constrained by hierarchies of partially specified machines. This allows for the use of prior knowledge to reduce the search space and provides a framework in which knowledge can be transferred across problems and in which component solutions can be recombined to solve larger and more complicated problems. Our approach can be seen as providing a link between reinforcement learn(cid:173) ing and "behavior-based" or "teleo-reactive" approaches to control. We present provably convergent algorithms for problem-solving and learn(cid:173) ing with hierarchical machines and demonstrate their effectiveness on a problem with several thousand states.
BibTeX
@inproceedings{parr1997reinforcement,
  author = {Ronald Parr and Stuart J. Russell},
  title = {{Reinforcement Learning with Hierarchies of Machines}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1997},
  url = {https://openreview.net/forum?id=rkW4bKZObS},
}
Figure