Source-linked AI summary
Hierarchical Imitation and Reinforcement Learning
Hoang M. Le, Nan Jiang, Alekh Agarwal, Miroslav Dudík, Yisong Yue, Hal Daumé
TL;DR
Long-horizon, sparse-reward tasks make reinforcement learning difficult, while imitation learning can require extensive demonstrations. The paper introduces hierarchical guidance, which allocates expert and reinforcement feedback across policy levels, and reports faster learning than hierarchical reinforcement learning with lower labeling cost than standard imitation learning.
Problem
Long-horizon sparse-reward decision-making is difficult from reinforcement signals alone, and existing imitation learning may require substantial demonstration data.
Method
Hierarchical guidance uses high-level expert feedback to focus low-level learning and supports different combinations of imitation and reinforcement learning across hierarchy levels.
Results
The approach learns faster than hierarchical reinforcement learning and is more label-efficient than standard imitation learning on long-horizon benchmarks, including Montezuma’s Revenge.
Takeaways & Limitations
Hierarchical guidance can speed learning and reduce the cost of expert feedback in hierarchical imitation learning and hybrid imitation–reinforcement learning.
Takeaways & Limitations
The hybrid approach relies on a subgoal termination predicate, which may need to be learned in some settings.
Abstract
from arXiv · showhide
We study how to effectively leverage expert feedback to learn sequential decision-making policies. We focus on problems with sparse rewards and long time horizons, which typically pose significant challenges in reinforcement learning. We propose an algorithmic framework, called hierarchical guidance, that leverages the hierarchical structure of the underlying problem to integrate different modes of expert interaction. Our framework can incorporate different combinations of imitation learning (IL) and reinforcement learning (RL) at different levels, leading to dramatic reductions in both expert effort and cost of exploration. Using long-horizon benchmarks, including Montezuma's Revenge, we demonstrate that our approach can learn significantly faster than hierarchical RL, and be significantly more label-efficient than standard IL. We also theoretically analyze labeling cost for certain instantiations of our framework.
1. Introduction
The paper asks how to leverage expert feedback effectively for long-horizon, sparse-reward decision-making. It proposes hierarchical guidance to reduce both exploration cost and expert effort by combining imitation and reinforcement learning across levels.
- Long horizons and sparse rewards make learning agent behavior from reinforcement signals alone particularly difficult.
- Existing imitation learning methods may require substantial demonstration data in long-horizon problems.
- Hierarchical guidance uses high-level expert feedback to focus low-level learning on necessary and relevant parts of the state space.
- The framework integrates imitation learning and reinforcement learning at different hierarchical levels to reduce expert effort and exploration cost.
2. Related Work
Related work spans passive and interactive imitation learning, hierarchical reinforcement learning, and combinations of imitation and reinforcement learning. This paper differs by applying feedback at multiple levels of a hierarchical policy.
- Imitation Learning: Imitation learning includes passive demonstration collection and interactive expert labeling along learner trajectories.
- Hierarchical Reinforcement Learning: Hierarchical reinforcement learning often assumes useful options are defined beforehand, whereas this agent learns subgoal policies through expert or reinforcement feedback.
- Combining Reinforcement and Imitation Learning: Prior imitation–reinforcement combinations mainly use imitation as flat-policy pre-training rather than assigning different feedback types across hierarchy levels.
3. Hierarchical Formalism
The formalism models a two-level agent that selects subtasks at a high level and executes primitive actions through subpolicies at a low level. It distinguishes expert feedback modes and their associated costs.
- Hierarchical Agent: The high-level policy chooses subtasks, while low-level policies execute primitive actions until subgoal termination.
- Trajectory Structure: A hierarchical trajectory contains high-level subgoal decisions and low-level trajectories, while the full trajectory concatenates all low-level trajectories.
- Expert Feedback: The expert may provide hierarchical demonstrations, high-level labels, low-level labels, low-level inspections, full labels, or full inspections.
- Feedback Costs: Inspect operations return Pass or Fail with less effort than labeling every action, and may take O(1) when checking a trajectory’s final state.
- Feedback Modes: HierDemo supports passive hierarchical behavioral cloning, while Label operations support interactive imitation learning and its hierarchical extensions.
- Feedback Costs: Label operations scale with trajectory length, with costs associated with high-level, low-level, and full-horizon labeling.
4. Hierarchically Guided Imitation Learning
Hierarchical guidance combines high-level supervision with selectively targeted low-level feedback, producing hierarchical behavioral cloning and hierarchically guided DAgger. The framework reduces expert labeling costs under hierarchical structure.
- Framework: Hierarchical guidance queries the low-level expert only when subtasks remain unmastered and restricts learning to relevant state-space regions.
- Algorithms: The framework yields hierarchical behavioral cloning for passive demonstrations and hg-DAgger for interactive imitation learning.
- hg-DAgger: hg-DAgger first checks full-task success, then labels high-level decisions and queries low-level labels only for failed subgoals along correct high-level choices.
- Theoretical Analysis: The theoretical analysis compares hg-DAgger with flat DAgger using finite policy classes and realizable expert policies.
- Cost Analysis: Both methods incur the same leading monitoring term, while hierarchical guidance reduces learning costs through cheaper inspections and shorter level-specific horizons.
- Cost Analysis: When HHI = HLO = √HFULL, hierarchical guidance reduces overall labeling cost by a factor of √HFULL.
5. Hierarchically Guided IL / RL
Hierarchical guidance combines high-level imitation with low-level reinforcement learning by using expert subgoal feedback to focus low-level learning on relevant experience.
- Hierarchically Guided IL / RL: Hierarchical guidance supports interactive IL at the high level and RL at the low level.The framework uses DAgger for the meta-controller and Q-learning for subpolicies.
- Hierarchically Guided IL / RL: High-level expert labels train the meta-controller and restrict low-level learning to states relevant to the selected subgoals.Experience accumulation stops when the meta-controller chooses a subgoal inconsistent with the expert’s choice.
- Hierarchically Guided IL / RL: The hybrid architecture is suited to settings where low-level expert labels are unavailable or more expensive than high-level labels.The high-level expert supplies the hierarchical decomposition and pseudo-reward function.
- Hierarchically Guided IL / RL: The low-level learner executes epsilon-greedy actions using subgoal-specific Q-functions and pseudo-rewards until each subgoal terminates.The algorithm updates Q-functions from minibatches while collecting low-level trajectories.
- Hierarchically Guided IL / RL: Pseudo-rewards assign positive value to successful subgoal completion, negative value to unsuccessful termination, and a small trajectory-length penalty otherwise.The success and termination predicates may be provided by an expert or learned from feedback.
6. Experiments
The paper evaluates hierarchical guidance on maze navigation and Montezuma’s Revenge, finding faster learning and reduced expert feedback relative to flat imitation and hierarchical RL baselines.
- Experiments: The evaluation covers a procedurally varied maze domain and the long-horizon Atari game Montezuma’s Revenge.The maze contains 16 rooms with varying connections, starts, and targets; Montezuma’s Revenge has sequential subgoals.
- Hierarchically Guided IL: Both h-BC and hg-DAgger outperform flat imitation learners, while hg-DAgger approaches 100% success in fewer than 1000 episodes.The reported curves summarize five random executions using median and minimum-to-maximum ranges.
- Hierarchically Guided IL: hg-DAgger reduces expert cost by concentrating low-level labels early and relying mainly on high-level labels after subgoals are mastered.It requires only a fraction of the low-level labels used by flat DAgger.
- Hierarchically Guided IL / RL: hg-DAgger/Q increasingly saves high-level feedback as successful inspections become more frequent, but initially requires more high-level labels because low-level Q-learning is slower.Figure 1 reports success rate and high-level label cost against the number of low-level RL samples.
- Montezuma’s Revenge: In Montezuma’s Revenge, h-DQN fails to reach success comparable to hg-DAgger/Q even with significantly more low-level samples, while flat Q-learning also fails.The four subgoals proceed from the right stair to the key, back to the stair, and then to the door.
- Montezuma’s Revenge: Human effort can be much smaller when the expert supplies the Montezuma subgoal sequence and detectors once, allowing high-level labeling to become automatic.The expert need only understand high-level semantics rather than provide action-level labels.
7. Conclusion
The paper presents hierarchical guidance as a framework for reducing expert-feedback costs in hierarchical imitation and hybrid imitation–reinforcement learning. It also identifies extensions to weaker feedback and an unresolved dependence on subgoal termination predicates.
- Hierarchical guidance can speed learning and reduce expert-feedback costs in hierarchical imitation learning and hybrid imitation–reinforcement learning.
- The framework can incorporate weaker preference, gradient-style, or bandit imitation feedback.
- The hybrid IL/RL approach assumes a subgoal termination predicate indicating when each subgoal is achieved.The predicate may be specified or learned, but learning it jointly with reinforcement-based action learning remains open.
- With only two initial subgoals, h-DQN still largely failed to learn the second subgoal.
A. Proofs
The proofs bound expert-feedback costs using mistake bounds from halving algorithms over hierarchical policy classes. The analysis separates full-trajectory inspection, high-level labeling, low-level labeling, and subgoal-selection errors.
- Full-task inspection incurs a cost each episode, while the number of episodes containing mistakes is bounded by the halving algorithm’s total mistakes.The relevant policy-class size is represented as log |M|+|G| log |ΠLO|.
- When full inspection finds issues, the expert labels subgoals and checks whether each subgoal was successfully accomplished, incurring low-level inspection cost.
- The number of such episodes is bounded by wrong-subgoal selections plus failures of subpolicies after correct subgoal choices.Wrong subgoals contribute at most log |M| events, while low-level mistakes contribute at most log |ΠLO| per good subgoal.
B. Additional Experimental Details
The additional experimental details specify how performance is averaged and how the maze and Montezuma’s Revenge experimental mechanisms are documented. Maze success rates are evaluated on held-out environments.
- Success rates and external rewards are reported as trailing averages over the previous 100 training episodes.
- Maze-navigation success rates are measured on separate test environments that were not used for training.
- The section describes subgoal detection or terminal predicates for Montezuma’s Revenge and maze-environment creation.Network architectures are provided in Tables 1 and 2.
B.1. Maze Navigation Domain
The maze experiments compare hg-DAgger/Q with h-DQN using matched network architectures, while giving h-DQN an artificial 50% horizon head-start. The hybrid method quickly outperforms h-DQN, which levels off at 30% success.
- The comparison uses hg-DAgger/Q and h-DQN with the same network architecture and an enhanced Q-learning procedure.
- The hybrid IL-RL method quickly outperforms h-DQN despite receiving no 50% head-start advantage, while h-DQN flattens at 30% success rate.The head-start gives h-DQN the optimal execution of the first half of each trajectory.
- The maze dataset contains 2000 environments, split into 1000 training maps and 1000 testing maps.Results use randomly selected environments from the 1000 test maps.
- Each maze begins as a 17×17 grid divided into a 4×4 room structure, and neural policies use a 17 × 17 pixel representation as input.
- Every generated environment has a feasible path from the start to the goal and a minimum start-to-goal distance of at least 40 steps.
B.1.2. HYPERPARAMETERS FOR MAZE NAVIGATION
The maze-domain implementation uses separate policy-network outputs for primitive actions and subgoals, with an additional termination classifier for each subgoal policy.
- Subgoal policy networks and the metacontroller differ only in their number of output classes: 4 actions versus 5 subgoals.
- Each subgoal policy includes a small termination-classification network that can be viewed as an additional policy-network head.
- The policy networks receive 3-channel pixel representations encoding the goal, agent, trail, and lava blocks with fixed values.
B.2. Montezuma’s Revenge
The Montezuma’s Revenge experiments combine high-level expert guidance with low-level reinforcement learning across four subgoals. The hybrid method learned substantially more effectively than h-DQN, although the fourth subgoal remained difficult under the computation limit.
- 81 of 100 experiments learned the first three subpolicies, while 89 of 100 learned the first two within 4 million low-level frames.The fourth subgoal was the most difficult, with almost half of experiments failing to learn it within the limit.
- The fourth subgoal’s longer horizon contributed to its difficulty, and introducing intermediate subgoals can shorten that horizon.
- All h-DQN experiments failed to master the second subgoal, even though the baseline was limited to only two subgoals.The comparison gave h-DQN the same network architecture and an enhanced Q-learning procedure.
- The hybrid algorithm generally outperformed h-DQN by a large margin on Montezuma’s Revenge.The comparison concerns hybrid IL-RL versus hierarchical RL, with reward and subgoal completion summarized across trials.
- HI-level expert advice prevents low-level reinforcement learners from accumulating bad experience, a problem that frequently affects h-DQN.
- Montezuma’s Revenge uses four landmark subgoals with automatic detectors, including a door detector that marks completion when at least 30% of box pixels change.