Hierarchical Reinforcement Learning (HRL)

An option is a temporally extended action, formalizing a subtask or skill. It consists of three components:

• Initiation Set: The states where the option can be started.
• Termination Condition: A function that determines when the option stops.
• Policy: The low-level policy that selects primitive actions while the option is executing.

This framework allows the agent to operate at a higher level of abstraction, treating the execution of an option as a single macro-action in a semi-Markov Decision Process (SMDP).

HAMs impose a programmable hierarchy on the agent's decision-making. A HAM is a finite-state machine where:

• States are machine states (like call, choice, stop).
• Transitions are governed by the machine's program, not learned probabilities.
• Learning is focused on the 'choice' states where the agent must select among sub-machines or primitive actions.

This approach constrains the policy space, drastically improving sample efficiency by reducing the number of decisions the agent must learn from scratch.

The MaxQ method decomposes the total action-value function Q(s, a) into a sum of value functions for subtasks. For a hierarchical policy with root task p, the value decomposition is: V^π(s) = V^π(p, s) = Σ_{c ∈ Children(p)} V^π(c, s)

Key Elements:

• Projected Value: The value of a subtask given its child's completion.
• Completion Function: Predicts the value after a subtask finishes.

This decomposition allows for off-policy learning within subtasks and enables subtask policies to be learned and reused independently.

FuNs implement a managerial hierarchy inspired by feudal systems. It features two levels:

• Manager: Operates at a lower temporal resolution. It sets abstract, goal-oriented sub-policies for the Worker by emitting a goal embedding in a latent state space.
• Worker: Executes primitive actions. It is intrinsically rewarded not for external reward, but for producing actions that align its internal state with the Manager's goal embedding.

This separation of concerns creates a skewed credit assignment, where the Manager learns long-term strategy and the Worker learns reusable skills to achieve directional goals.

A central challenge in HRL is how higher levels specify goals for lower levels. This is often addressed through intrinsic motivation.

Common Approaches:

• Goal-Conditioned Policies: Lower-level policies are trained to reach any state specified as a goal (e.g., π_low(a | s, g)).
• Sparse Reward Shaping: The high-level agent provides a sparse reward only when the low-level agent achieves the precise subgoal.
• Hindsight Experience Replay (HER): Even on failed episodes, experiences are relabeled with achieved states as goals, dramatically improving sample efficiency for goal-conditioned skills.

Instead of a pre-defined hierarchy, methods exist to discover useful skills from interaction data, forming the hierarchy automatically.

Key Techniques:

• Variational Intrinsic Control: Learns skills that maximize empowerment (the mutual information between skills and resulting states).
• Diversity is All You Need (DIAYN): Discovers skills by maximizing the mutual information between states and a latent skill variable z, encouraging diverse, distinguishable behaviors.
• Option-Critic Architecture: Learns the option's internal policy, termination condition, and the high-level policy over options end-to-end via gradient descent, without pre-defining subgoals.

The Options Framework is the foundational formalism for HRL, introducing the concept of temporally extended actions. An option is a triple (I, π, β) where:

• I is the initiation set (states where the option can start).
• π is the intra-option policy (the low-level skill).
• β is the termination condition (probability of stopping in a state).

This creates a Semi-Markov Decision Process (SMDP), where the high-level policy selects among options, and time elapses until the option terminates. It enables temporal abstraction by treating multi-step skills as single, choosable actions at a higher level.

MAXQ decomposes the value function of the overall task hierarchically. It breaks the main MDP into a directed acyclic graph of subtasks. Each subtask has its own:

• Termination predicate.
• Local reward function (often zero, with reward only at root).
• Child subtasks or primitive actions.

The projected value function for a parent task is the sum of the values of executing its child tasks. This allows for state abstraction within subtasks, ignoring irrelevant parts of the state space, and enables more efficient learning and transfer of sub-skills.

Hierarchical Abstract Machines (HAMs) constrain the space of possible policies through programmable machines, providing a strong bias for faster learning. A HAM is a finite-state controller with:

• Machine states (like 'choice', 'call', 'stop').
• Transitions that can call other HAMs (subroutines) or execute primitive actions.

The learning agent only needs to resolve the choices left open by the machine (e.g., which action in a 'choice' state), rather than learning a policy from scratch. This makes it particularly effective in Partially Observable MDP (POMDP) settings where the machine provides memory.

Feudal Reinforcement Learning structures the hierarchy like a feudal system, where a manager sets goals for a sub-manager or worker. The key innovation is the use of goal-conditioned policies at each level.

• The manager does not specify how to achieve a goal, only what the subgoal should be.
• The subordinate learns a policy to achieve any commanded subgoal.
• Reward is given only at the top level for the final task. This enforces a strict information hiding principle, where lower levels are unaware of the global objective, promoting modularity and skill reuse.

A major challenge in HRL is designing the hierarchy. Skill discovery algorithms automate this process. Common approaches include:

• Betweenness: Identifying states that are frequently visited on paths between random states as potential subgoals.
• Variational Intrinsic Control: Maximizing the mutual information between skills and resulting states to learn diverse, distinguishable skills.
• Diversity-Based: Encouraging the learning of skills that lead to different regions of the state space.

These methods enable unsupervised pre-training of a library of reusable skills before tackling a specific downstream task.

Modern deep HRL often implements hierarchies using actor-critic architectures with multiple levels. For example, a Hierarchical Actor-Critic (HAC) or HIRO algorithm features:

• A high-level critic that evaluates the high-level policy selecting goals.
• A high-level actor that proposes subgoals for a lower temporal resolution.
• A low-level critic & actor that learns a goal-conditioned policy to achieve the proposed subgoals.

The low-level policy is trained with an intrinsic reward based on subgoal achievement, while the high-level policy is trained on the extrinsic task reward. This requires careful off-policy correction to align the high-level's goals with the low-level's learned capabilities.

The foundational mathematical framework for modeling sequential decision-making. An MDP is defined by a tuple (S, A, P, R, γ):

• S: A set of states.
• A: A set of actions.
• P: Transition probabilities, P(s'|s,a).
• R: A reward function, R(s,a,s').
• γ: A discount factor. It assumes the Markov property, where the future depends only on the present state. HRL frameworks are built on top of MDPs, treating subtasks as smaller MDPs or semi-Markov Decision Processes (SMDPs).

A formalization within HRL where temporally extended actions, called options, are defined by a triple (I, π, β).

• I: The initiation set of states where the option can start.
• π: The intra-option policy.
• β: The termination condition, a probability of stopping in each state. This framework provides a rigorous theory for temporal abstraction, allowing high-level policies to choose among options, which then execute their own policies until termination. It's a core model for implementing skill hierarchies.

A specific HRL architecture inspired by feudal systems, where a hierarchy of managers and sub-managers operate at different levels of temporal and spatial abstraction.

• A manager at a high level sets sub-goals for a lower-level worker.
• The worker learns a policy to achieve these sub-goals.
• Communication is often via a goal representation space. This structure enforces a clean separation of concerns and can improve learning efficiency by constraining the search space for each level of the hierarchy.

A method for decomposing the value function of a large MDP into the sum of value functions for individual subtasks. Developed as part of the MAXQ hierarchy, it breaks the Q-value of a composite task into:

• The completion value of the current subtask.
• The Q-value of the child action being executed. This additive decomposition allows for off-policy learning and provides a principled way to share learned sub-policies across multiple parent tasks, promoting reuse and transfer learning.

A programming-language-inspired approach to HRL where the agent's behavior is constrained by a machine hierarchy. A HAM is a finite-state machine with nondeterministic choice points.

• The hierarchy specifies allowable sequences of actions, restricting the policy search space.
• Learning focuses on resolving the nondeterministic choices to maximize reward. This method incorporates partial programs or sketches to inject prior knowledge, guiding exploration and accelerating learning in complex domains.

An HRL paradigm where policies at multiple levels are conditioned on goals. A high-level policy selects a sub-goal for a lower-level goal-conditioned policy to achieve.

• Enables zero-shot or few-shot generalization to new goals.
• Sub-goals are often defined in a learned latent space or a subset of the state space.
• Closely related to hindsight experience replay (HER), where failed trajectories are relabeled with achieved goals as learning examples. This is crucial for learning reusable skills in sparse-reward environments.