Learning Multi-Level Hierarchies with Hindsight

Andrew Levy, George Dimitri Konidaris, Robert Platt Jr., Kate SaenkoICLR 2019 · OpenReview

Overview

The Hierarchical Actor-Critic (HAC) framework allows agents to learn multiple levels of a policy hierarchy simultaneously and in parallel. By using "hindsight" to simulate optimal lower-level behavior while grounding subgoals in reality through testing, HAC becomes the first algorithm to successfully train three-level hierarchies in continuous state and action spaces.

The "Moving Target" Problem in HRL

Reinforcement Learning (RL) often struggles with "long-horizon" tasks—problems where a long sequence of precise actions is required to reach a distant goal, such as a robot navigating through a maze of rooms. Hierarchical Reinforcement Learning (HRL) aims to solve this by breaking tasks down into manageable subgoals.

However, HRL suffers from a "moving target" problem: if you try to learn all levels of the hierarchy at once, the higher levels become unstable. A high-level policy might pick a perfectly valid subgoal, but if the low-level policy hasn't yet learned how to reach it, the high-level policy receives a failure signal and incorrectly assumes its choice was bad. Historically, researchers bypassed this by training bottom-up (one level at a time), which is notoriously slow and sample-inefficient.

Hierarchical Actor-Critic (HAC)

The authors introduce Hierarchical Actor-Critic (HAC) to overcome this instability. The core innovation is a trio of transition types that allow different levels of the hierarchy to learn independently:

Hindsight transitions allow the agent to learn from achieved states rather than just intended goals.
  1. Hindsight Action Transitions: This mechanism stabilizes parallel learning. When a high-level policy proposes a subgoal but the low-level policy fails and ends up at a different state, HAC records a transition as if the high-level policy intended to go to that achieved state. This allows the high level to learn the physics of the world (where actions actually lead) as if it had an optimal low-level controller, even while the real controller is still learning.
  2. Hindsight Goal Transitions: An extension of Hindsight Experience Replay (HER). If an agent fails to reach a final goal, it re-labels the experience with the state it actually reached, ensuring it always receives a meaningful reward signal.
  3. Subgoal Testing Transitions: To prevent the high-level policy from proposing physically impossible "teleportation" subgoals, HAC occasionally forces the agent to use its current lower-level policy without any hindsight tricks. If it fails, it receives a heavy penalty, grounding the hierarchy in the agent's actual capabilities.

Architecture and Environments

The architecture uses nested, goal-conditioned policies where each level (except the bottom) outputs a state in the environment as a subgoal for the level below it. The bottom level outputs primitive actions (e.g., joint torques).

A 3-level policy hierarchy applied to the complex Ant Four Rooms navigation task.

The researchers evaluated HAC on discrete grid worlds and continuous MuJoCo robotics environments, including an Inverted Pendulum, a UR5 Reacher, and an Ant Reacher. The most complex task was the Ant Four Rooms, requiring a quadruped robot to navigate a maze.

Key Results and Insights

  • Simulating Optimality: The most profound insight is that a high-level manager can be trained by pretending its subordinates are already perfect. By using the achieved state as the "intended action," the manager learns the environment's map regardless of the subordinate's current skill level.
  • 3-Level Success: HAC is the first framework to successfully learn 3-level hierarchies in continuous spaces. In the Ant Four Rooms task, the 3-level agent significantly outperformed the 2-level agent, which in turn crushed the non-hierarchical "flat" agent.
  • Beating the State-of-the-Art: HAC demonstrated faster learning and higher peak performance across multiple continuous control tasks compared to HIRO, another leading HRL algorithm.
  • Sparse Reward Mastery: HAC excels in environments with sparse rewards (where the agent only gets a signal upon total success), a notoriously difficult setting for standard RL.

Limitations and Future Work

While powerful, HAC introduces new hyperparameters, such as the maximum subgoal horizon and the subgoal testing rate, which require tuning. Additionally, the "achievement" of a goal is currently determined by hand-crafted distance thresholds, and the hierarchy depth is fixed. Future work could involve learning these thresholds dynamically or allowing the system to automatically add or remove hierarchy levels based on task complexity.

Summary updated

Abstract

Hierarchical agents have the potential to solve sequential decision making tasks with greater sample efficiency than their non-hierarchical counterparts because hierarchical agents can break down tasks into sets of subtasks that only require short sequences of decisions. In order to realize this potential of faster learning, hierarchical agents need to be able to learn their multiple levels of policies in parallel so these simpler subproblems can be solved simultaneously. Yet, learning multiple levels of policies in parallel is hard because it is inherently unstable: changes in a policy at one level of the hierarchy may cause changes in the transition and reward functions at higher levels in the hierarchy, making it difficult to jointly learn multiple levels of policies. In this paper, we introduce a new Hierarchical Reinforcement Learning (HRL) framework, Hierarchical Actor-Critic (HAC), that can overcome the instability issues that arise when agents try to jointly learn multiple levels of policies. The main idea behind HAC is to train each level of the hierarchy independently of the lower levels by training each level as if the lower level policies are already optimal. We demonstrate experimentally in both grid world and simulated robotics domains that our approach can significantly accelerate learning relative to other non-hierarchical and hierarchical methods. Indeed, our framework is the first to successfully learn 3-level hierarchies in parallel in tasks with continuous state and action spaces.
BibTeX
@inproceedings{levy2019learning,
  author = {Andrew Levy and George Dimitri Konidaris and Robert Platt Jr. and Kate Saenko},
  title = {{Learning Multi-Level Hierarchies with Hindsight}},
  booktitle = {International Conference on Learning Representations},
  year = {2019},
  url = {https://openreview.net/forum?id=zGb0js4aaRP},
}
Figure