Source-linked AI summary
Learning Multi-Level Hierarchies with Hindsight
Andrew Levy, George Konidaris, Robert Platt, Kate Saenko
TL;DR
Hierarchical agents could learn more efficiently by solving shorter subtasks, but parallel learning across levels is difficult when lower-level changes alter higher-level transitions. HAC uses nested policies and hindsight transitions to train levels simultaneously; it reports better performance with deeper hierarchies across grid-world and simulated-robotics tasks, including continuous tasks.
Problem
Although hierarchical agents can decompose tasks into shorter subtasks, existing automatically learned hierarchies in continuous domains often train levels sequentially rather than in parallel.
Source: §1 · p. 1Method
HAC uses nested goal-conditioned policies and hindsight action and goal transitions to train multiple levels independently of changing lower-level policies, including with sparse rewards.
Source: §1 · pp. 2–3Results
Across grid-world and simulated-robotics tasks, multi-level agents outperformed single-policy agents, 3-level agents outperformed 2-level agents, and HAC outperformed HIRO on three simulated robotics tasks.
Source: §1 · p. 3Takeaways & Limitations
The results support HAC’s potential to improve sample efficiency, including by jointly learning 3-level policies in continuous-state and continuous-action tasks.
Source: §6 · p. 10Hindsight transitions restrict a level’s learned subgoal actions to states achievable within H actions by the level below, leaving more distant subgoals unlearned.
Source: §4.5 · p. 7
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
HAC targets the instability that makes parallel learning across hierarchical levels difficult, using hindsight transitions so levels can learn simultaneously. Its hierarchy passes subgoals downward, and experiments report gains across grid-world and simulated-robotics tasks.
1 INTRODUCTION
- Existing automatically learned hierarchies in continuous domains often train levels one at a time, despite the potential for shorter subproblems to accelerate learning.The paper argues that realizing this potential requires learning multiple levels in parallel.Source: §1 · p. 1
- Parallel hierarchical learning is difficult because changing lower-level policies change the transition functions faced by higher levels.RL can struggle to value higher-level actions when the distribution of states they reach is unstable.Source: §1 · pp. 1–2
- HAC uses nested goal-conditioned policies that pass subgoal states downward until the lowest-level policy outputs a primitive action.Each level stops when it achieves its goal or runs out of attempts, after which the level above may issue another subgoal.Source: §1 · p. 2
- Hindsight action transitions replace a proposed subgoal with the state actually achieved, while hindsight goal transitions use an achieved state as the goal.These transitions support parallel policy learning with sparse rewards by simulating transitions as if lower-level policies were optimal and relabeling goals.Source: §1 · p. 3
- In grid-world and simulated-robotics tasks, HAC’s multi-level agents outperformed single-policy agents, and 3-level agents outperformed 2-level agents.The paper also reports that HAC was the first to jointly learn 3-level policies in tasks with continuous state and action spaces, and that it outperformed HIRO on three simulated robotics tasks.Source: §1 · p. 3
2 RELATED WORK
Prior hierarchical reinforcement-learning approaches have limitations in domain coverage and training requirements. HAC is positioned against methods that train levels sequentially, build options incrementally, or omit hindsight transitions.
2 RELATED WORK
- Many earlier hierarchical reinforcement-learning approaches either work only in discrete domains, require pretrained low-level controllers, or need an environment model.The paper frames automatically learning hierarchical policies as a longstanding reinforcement-learning problem.Source: §2 · p. 3
- Schmidhuber’s method trains levels bottom-up, Skill Chaining builds options incrementally, and HIRO omits hindsight transitions in sparse-reward tasks [Nachum et al., 2018].The paper contrasts HAC’s parallel option learning with Skill Chaining and reports that HAC outperformed HIRO on three simulated robotics tasks elsewhere in the paper.Source: §2 · p. 3
3 BACKGROUND
The background formalizes goal-conditioned reinforcement learning and introduces function approximation and replay techniques used for continuous, sparse-reward settings.
3 BACKGROUND
- A Universal MDP augments an MDP with a set of goals, selecting one goal for the episode and optimizing a policy conditioned on state and goal.The goal may be a state or a set of states.Source: §3 · p. 4
- Universal Value Function Approximators estimate goal-conditioned action values and may generalize Q-values across state, goal, and action regions.The paper notes that this generalization is less helpful when sparse rewards are rarely achieved.Source: §3 · p. 4
- Hindsight Experience Replay copies off-policy transitions and replaces the original goal with a state achieved during the episode, creating transitions with sparse reward.These transitions help the UVFA learn regions with higher Q-values that it may generalize to other regions.Source: §3 · p. 4
4 HIERARCHICAL ACTOR-CRITIC (HAC)
HAC transforms a hierarchical decision problem into level-specific UMDPs so nested policies can be learned in parallel. Its transitions use hindsight to support learning under changing lower-level policies and sparse rewards.
4 HIERARCHICAL ACTOR-CRITIC (HAC)
- HAC transforms the original UMDP into k level-specific UMDPs so each policy can be learned in parallel.The hierarchy contains k policies, with k chosen by the user.Source: §4 · p. 4
4.1 STATE, GOAL, AND ACTION SPACES
- Each level uses the same state and goal spaces; higher levels output subgoal states, while the bottom level outputs primitive actions.For levels above the bottom, the action space is the state space; the bottom-level action space is the task's primitive-action space.Source: §4.1 · p. 4
4.2 NESTED POLICIES
- A higher-level transition embeds the policy below it, which gets at most H attempts to reach the subgoal before the transition ends.Because each lower-level policy depends on the level beneath it, a higher-level transition depends on the full lower-level hierarchy.Source: §4.2 · p. 5
4.3 HINDSIGHT ACTION TRANSITIONS
- Hindsight action transitions substitute the state actually reached for the proposed subgoal, helping higher levels learn against an optimalized lower-level transition rather than changing current policies.Their reward depends on the reached state and goal, not the path taken by lower levels.Source: §4.3 · p. 6
4.4 HINDSIGHT GOAL TRANSITIONS
- Hindsight goal transitions relabel transitions with a reached state as the goal, creating sparse-reward examples for each level.The method copies transitions, selects a next state as the new goal, and updates the reward accordingly.Source: §4.4 · pp. 6–7
4.5 SUBGOAL TESTING TRANSITIONS
- Hindsight alone leaves distant subgoals unlearned and may favor paths current lower-level policies cannot execute; subgoal testing penalizes unachieved subgoals and favors currently achievable paths.Testing follows the current lower-level policy exactly; if the subgoal is not reached within H actions, the level receives a penalty.Source: §4.5 · pp. 7–8
- Subgoal testing assigns distant, unattainable-within-H subgoals a Q-value target of −H, rather than leaving those actions' values ignored.For subgoals requiring more than H actions even under an optimal lower-level policy, the penalty transition is the only transition received for those tuples.Source: §4.5 · p. 8
4.6 ALGORITHMS
- The appendix provides HAC's full procedure and implementation details, and a discrete version called Hierarchical Q-Learning.The full procedure and discrete algorithm are given as Algorithms 1 and 2.Source: §4.6 · p. 8
5 EXPERIMENTS
The experiments compare flat, two-level, and three-level agents across grid-world and simulated robotics tasks, then assess HAC against HIRO and ablate subgoal testing. Across tasks, deeper HAC hierarchies outperform shallower ones, and two-level HAC also outperforms HIRO in the tested robotics tasks.
5 EXPERIMENTS
- The evaluation covered grid-world tasks and four MuJoCo robotics tasks, comparing flat Q-learning or DDPG agents using HER with hierarchical agents.The robotics tasks were inverted pendulum, UR5 reacher, ant reacher, and ant four rooms.Source: §5 · p. 8, §5.1 · p. 9
5.1 RESULTS
- Across all tasks, 3-level agents outperformed 2-level agents, which outperformed flat agents; HAC also significantly outperformed flat agents.Figure 4 reports average episode success rates; discrete-task averages use 50 trials and continuous-task averages use at least 7.Source: Figure 4 · p. 9, §5.1 · p. 9
5.1.1 BASELINE COMPARISON
- The 2-level HAC agent significantly outperformed HIRO on the inverted pendulum, UR5 reacher, and ant reacher tasks.Figure 5 compares their average success rates with 1-standard-deviation error bars.Source: Figure 5 · p. 10, §5.1.1 · p. 10
5.1.2 SUBGOAL TESTING ABLATION STUDIES
- Subgoal-testing HAC significantly outperformed both no-subgoal-testing and always-penalize-missed-subgoal baselines.The always-penalize baseline applies penalties even when lower levels use noisy policies to attempt subgoals.Source: §5.1.2 · p. 10
6 CONCLUSION
HAC targets parallel learning across hierarchy levels by training each level as though lower levels were already optimal. Results across discrete and continuous domains report improved sample efficiency, including the first empirically learned 3-level policies in continuous-state and continuous-action tasks.
6 CONCLUSION
- HAC trains each hierarchy level as if the lower levels were already optimal, addressing instability during simultaneous multi-level learning.The framework is evaluated in several discrete and continuous domains.Source: §6 · p. 10
- Across several discrete and continuous domains, the results confirm that HAC can significantly improve sample efficiency.Source: §6 · p. 10
- HAC was the first framework reported to learn 3-level hierarchical policies in parallel in tasks with continuous state and action spaces.Source: §6 · p. 10
7 APPENDIX
The appendix specifies HAC and HierQ training procedures, formalizes level-specific UMDPs and transitions, and reports subgoal-testing ablations and implementation settings.
7.1 HIERARCHICAL ACTOR-CRITIC (HAC) ALGORITHM
- HAC trains k actor and critic functions across hierarchy levels, recursively passes each level’s subgoal downward, and records tested misses, achieved-state hindsight actions, and hindsight relabelings.Training updates all actor and critic networks after episodes; each level attempts its subgoal for up to H steps or until a higher-level goal is achieved.Source: §7.1 · p. 12
7.2 HIERARCHICAL Q-LEARNING (HIERQ) ALGORITHM
- HierQ targets discrete state and action spaces, omits subgoal testing, and uses pessimistic Q-value initialization to discourage proposing subgoals too distant to achieve.Its stated initialization bounds each level’s Q-values by −H^(i+1).Source: §7.2 · p. 13
7.3 UMDP TUPLE DEFINITIONS
- Level 0 retains the original state, action, and transition spaces with every state as a potential goal; higher levels output state-valued subgoals and define hindsight and current-policy transitions.Higher-level rewards include penalties for missed subgoals only during subgoal testing.Source: §7.3 · p. 14
7.4 UMDP STATE TRANSITION FUNCTION
- The state-transition procedure recursively executes the lower-level policy for up to H actions, returning when the iteration limit is reached or a hierarchy goal is achieved.Otherwise, it continues executing actions from the policy at that level.Source: §7.4 · p. 14
7.5 SUBGOAL TESTING ABLATION STUDIES
- Always penalizing missed subgoals under noisy lower-level policies performed significantly worse; without testing, policies proposed targets unreachable within H actions, forcing long action sequences.Figure 6 compares the authors’ implementation with no testing and with always penalizing missed subgoals, using 3-level agents.Source: §7.5 · pp. 14–15, Figure 6 · p. 15
7.6 HIERARCHICAL ACTOR-CRITIC IMPLEMENTATION DETAILS
- Implementation bounded each critic’s outputs to [−H, 0], sampled 20% of actions uniformly from the level’s action space, set subgoal-testing rate λ = 0.3, and generally used H ∈ [20,30] for two-level MuJoCo agents.Source: §7.6 · pp. 15–16