Abstract
In the context of hierarchical reinforcement learning, the idea of hierarchies of abstract machines (HAMs) is to write a partial policy as a set of hierarchical finite state machines with unspecified choice states, and use reinforcement learning to learn an optimal completion of this partial policy. Given a HAM with potentially deep hierarchical structure, there often exist many internal transitions where a machine calls another machine with the environment state unchanged. In this paper, we propose a new hierarchical reinforcement learning algorithm that discovers such internal transitions automatically, and shortcircuits them recursively in computation of Q values. The resulting HAMQ-INT algorithm outperforms the state of the art significantly on the benchmark Taxi domain and a much more complex RoboCup Keepaway domain.
Introduction
Reinforcement Learning (RL) often struggles with the "curse of dimensionality" in complex environments. Hierarchical Reinforcement Learning (HRL) addresses this by allowing designers to provide a "partial policy" or a hierarchy of tasks. One popular framework is Hierarchies of Abstract Machines (HAMs), where the agent's behavior is defined by nested finite state machines.
However, deep hierarchies—while easier for humans to design—introduce a hidden efficiency cost. When a "parent" machine calls a "child" machine, the agent's internal stack changes, but the environment state remains the same. Standard algorithms treat these "internal transitions" as full steps in a Semi-Markov Decision Process (SMDP). This leads to redundant computation and slower convergence because the agent has to "learn" transitions that are actually deterministic and cost-free by design.
Methods: HAMQ-INT
The authors propose HAMQ-INT, which leverages these internal transitions to accelerate learning. The core idea is to identify and "short-circuit" moments where an agent changes its internal state (like calling a sub-routine) without changing the environment.
The algorithm operates through three key mechanisms:
- Automatic Discovery: The algorithm tracks a global environment clock. If the agent moves between "choice points" (states where it must make a decision) but the clock hasn't advanced, it identifies an internal transition.
- Predicate Generalization: Instead of just remembering that a specific state $s$ leads to an internal transition, the algorithm tracks which predicates (logical conditions like
is_at_destination) were evaluated. This allows the agent to generalize: if the same conditions are met in a different state, it knows the same internal transition will occur. - Recursive Short-Circuiting: When calculating the value of a state ($Q$-value), if the agent knows an internal transition is coming, it doesn't wait to experience it. Instead, it recursively computes the $Q$-value by looking ahead to the next choice point where an actual environment action will occur. This effectively collapses a tree of internal machine logic into a single Bellman backup.
Experimental Evaluation
The researchers evaluated HAMQ-INT on two primary benchmarks:
- The Taxi Domain: A classic HRL benchmark where a taxi must pick up and drop off passengers in a grid world. The authors added complexity by requiring the taxi to choose between different speeds and navigation strategies.
- RoboCup Keepaway: A much more complex, multi-agent domain with continuous state spaces. A team of "keepers" must maintain possession of a ball while "takers" try to intercept it.
Deep hierarchies are a double-edged sword: while they make it easier for humans to encode prior knowledge, they create more "internal noise" for standard RL algorithms. HAMQ-INT turns this weakness into a strength by exploiting the deterministic nature of the hierarchy. Since internal transitions always have a reward of zero and take zero environment time, the algorithm treats the hierarchy as a set of logical rules rather than a black-box environment.
Key Results
In the Taxi Domain, HAMQ-INT outperformed standard HAMQ and MAXQ (another popular HRL framework) significantly. It reached optimal performance much faster, particularly in the early stages of learning.
In the RoboCup Keepaway environment, Concurrent-HAMQ-INT (a multi-agent version) outperformed both standard HAMQ and "Option-based" learning. It achieved a higher average episode duration and converged after about 15 hours of training, whereas other methods lagged behind or plateaued lower.
Conclusion
HAMQ-INT demonstrates that recognizing the deterministic structure of hierarchical policies can lead to significant gains in learning efficiency. While the performance is dependent on the quality of the human-provided hierarchy and the selection of relevant predicates, the "short-circuiting" logic provides a powerful way to focus learning capacity on unpredictable environment interactions. Future work may involve automatically discovering these predicates or the hierarchy itself to reduce reliance on prior knowledge.
Summary updated