Hierarchical RL and Temporal Abstraction

"I do not walk to the kitchen one muscle twitch at a time. I issue an order, 'go to the kitchen', and let some subordinate worry about the thousand little steps. When it reports back, I issue the next order. I am paid to choose goals, not footsteps, and the secret of my productivity is that I never once read the footnotes."

A Manager Policy Delegating the Boring Steps to Its Subordinates

In Section 26.4 we bounded an agent's risk with explicit constraints, keeping it inside a safety budget with constrained, Lagrangian methods. This section changes the unit of decision entirely. Instead of asking the agent to choose better primitive actions, we let it choose behaviors: sequences of primitive actions, bundled and named, selected as wholes. That single move, from acting over actions to acting over temporally-extended actions, is the content of hierarchical reinforcement learning, and it is the most direct structural answer the field has to the problem that flat RL handles worst: the long horizon with a sparse reward. We use the unified notation of Appendix A throughout: $s$ a state, $a$ a primitive action, $\pi$ a policy, $r$ a reward, $\gamma$ the discount, and we add $o$ for an option and $g$ for a subgoal.

Why does temporal abstraction deserve its own section rather than a remark that "you can group actions"? Because grouping actions correctly changes the mathematics of the problem, not just its engineering. An option that runs for a random number of steps turns the discrete-time MDP of Chapter 22 into a semi-Markov process whose value equations must discount over duration, it changes what a Bellman backup means, and it changes the effective horizon over which credit must travel from thousands of primitive steps to a handful of option choices. Get the abstraction right and a task that was hopeless for a flat agent becomes routine; get it wrong (options that never terminate, subgoals the worker cannot reach, a manager that learns faster than its worker) and the hierarchy is worse than the flat baseline it replaced. This section gives you the theory to reason about that boundary and the code to sit on the right side of it.

The competencies this section installs are four. To state precisely why flat RL's credit-assignment difficulty grows with the horizon and the reward sparsity. To define an option as an initiation-set, intra-option-policy, termination triple and to write the SMDP Bellman equations that value options. To place the modern HRL architectures (option-critic, FeUdal, HIRO, skill discovery) on a single map of "where does the abstraction come from". And to implement a two-level hierarchy from scratch and verify it solves a sparse-reward task a flat agent cannot. These are the load-bearing skills for the control-and-imitation methods of Chapter 27 and the planning-over-abstractions of Chapter 29.

1. The Long-Horizon, Sparse-Reward Problem and Why Flat RL Struggles Beginner

A flat reinforcement learner chooses one primitive action at every timestep and learns from the reward signal that follows. On a task where reward is dense (something informative arrives almost every step) this is fine: the gradient of return with respect to each decision is well estimated because feedback is frequent and local. The trouble begins when the reward is sparse and the horizon is long: the agent must execute a long, specific sequence of primitive actions before any reward distinguishes success from failure, and until that reward arrives every action looks equally good or bad. Credit for the eventual outcome must then be assigned backward across the entire chain, and the longer the chain, the thinner the signal that reaches its early links.

This is the control-theoretic twin of a pathology we have already met. In Section 9.4 we saw that a recurrent network propagating a gradient backward across many timesteps multiplies one Jacobian per step, and the product vanishes (or explodes) geometrically with depth, so a learning signal from the distant future barely reaches the distant past. Temporal-difference credit assignment in a long-horizon MDP has the same shape: bootstrapped value information seeps backward one Bellman backup per step, discounted by $\gamma$ each time, so a reward $H$ steps away is attenuated by $\gamma^{H}$ before it influences an early decision. With $\gamma = 0.99$ and $H = 1000$ that factor is $\gamma^{H} \approx e^{-10} \approx 4.5 \times 10^{-5}$: the reward is, for practical purposes, invisible to the actions that earned it. Long-horizon RL is BPTT's long-dependency problem wearing a control costume.

Compounding the attenuation is exploration. To even observe the sparse reward once, a flat agent acting by local exploration (epsilon-greedy, or small policy noise) must stumble onto the entire successful sequence by chance. If success requires a specific length-$H$ sequence over $|\mathcal{A}|$ actions, the probability of hitting it by undirected exploration is on the order of $|\mathcal{A}|^{-H}$, which is astronomically small for any non-trivial $H$. The agent cannot learn from a reward it never sees, and it cannot reliably see a reward that demands a long precise sequence. The two difficulties reinforce each other: sparse reward starves credit assignment, and the long horizon starves exploration.

Temporal abstraction is the structural fix. If the agent could commit to a behavior that runs for many primitive steps, then at the level where it makes decisions the horizon collapses: a task that was a thousand primitive steps deep might be only a handful of option choices deep, and credit must travel across that handful, not the thousand. The discount seen at the option level is $\gamma$ raised to the option's duration rather than to a single step, so reward that was attenuated by $\gamma^{1000}$ at the primitive level might be attenuated by only $\gamma^{3}$ at a three-option level. Acting at multiple time scales is therefore not a convenience but a direct shortening of the chain over which credit must propagate, exactly as Figure 26.5.1 contrasts. The rest of this section makes "a behavior that runs for many steps" mathematically precise and then builds one.

2. The Options Framework and the Semi-MDP View Intermediate

The classical formalization of a temporally-extended action is the option, introduced by Sutton, Precup, and Singh. An option $o$ is a triple

where the three components answer three questions about the behavior. The initiation set $\mathcal{I}_o \subseteq \mathcal{S}$ says where the option may begin: the option is available for selection only in states $s \in \mathcal{I}_o$. The intra-option policy $\pi_o(a \mid s)$ says what the option does while it runs: a policy over primitive actions that executes until termination. The termination condition $\beta_o(s) \in [0,1]$ says when the option ends: the probability that the option stops upon reaching state $s$, returning control to the level above. A primitive action is the degenerate special case of an option that is available everywhere, takes exactly one action, and always terminates after one step ($\beta_o \equiv 1$), so options strictly generalize actions and a flat MDP is an HRL problem with only one-step options.

An agent equipped with a set of options $\mathcal{O}$ chooses among them with a policy over options $\mu(o \mid s)$, which selects an option in an initiation state, runs that option's intra-option policy until it terminates, then chooses the next option, and so on. Crucially the options run for a random number of primitive steps $\tau$ (random because $\beta_o$ is stochastic and the environment is stochastic), and this is what takes us out of the ordinary discrete-time MDP. A process in which actions take random, state-dependent amounts of time is a semi-Markov decision process (SMDP), and the value functions of an SMDP discount over those durations.

Concretely, define for an option $o$ started in state $s$ two SMDP quantities: the expected discounted reward accumulated while the option runs, and the discounted distribution over the state where it terminates. Let $\tau$ be the (random) option duration and $r_{t+1}, \dots, r_{t+\tau}$ the primitive rewards collected. Write the option's reward model and transition model as

where $R_o(s)$ is the discounted reward earned during the option and $P_o(s' \mid s)$ folds the discount $\gamma^{\tau}$ over the random duration into the transition itself (so $P_o$ is a sub-stochastic, discount-weighted kernel, not a probability distribution). With these two models the option-level Bellman equations have exactly the shape of the ordinary ones, but over options rather than primitive actions:

The optimal option-value equation is the same backup with a max over options available in the initiation set,

and a single SMDP $Q$-learning update, after running an option from $s$ to its termination at $s'$ in $\tau$ steps and collecting accumulated discounted reward $G = \sum_{i=1}^{\tau}\gamma^{i-1} r_{t+i}$, is

This is ordinary $Q$-learning with two modifications, and both come from the option running for $\tau$ steps rather than one: the immediate reward is the accumulated discounted reward $G$ over the whole option, and the bootstrap discount is $\gamma^{\tau}$ rather than $\gamma$. Setting $\tau \equiv 1$ recovers flat $Q$-learning exactly, which is the precise sense in which the SMDP view generalizes Chapter 22. The decisive consequence is the one Section 1 anticipated: because the bootstrap discount is $\gamma^{\tau}$ with $\tau$ often large, value information jumps many primitive steps in a single backup, so credit propagates across the episode in a number of updates proportional to the option count rather than the primitive-step count.

Two subtleties matter in practice. First, the option models $R_o$ and $P_o$ are usually not known and must be learned, which is what the intra-option learning methods and the option-critic of Section 3 do. Second, the SMDP view above treats each option as atomic (decisions are made only at option boundaries), but intra-option methods can update an option's value and policy at every primitive step it executes, which is far more data-efficient because every step teaches, not just every boundary. The option-critic of the next subsection is exactly an intra-option, end-to-end-differentiable realization of this idea.

3. Modern HRL: Option-Critic, FeUdal, HIRO, and Skill Discovery Advanced

The classical options framework assumes the options are given. The central question of modern HRL is the opposite: where do the options come from? Four major families answer it differently, and they organize cleanly along that axis.

Learn the options end to end (the option-critic). Bacon, Harb, and Precup's option-critic (2017) makes the intra-option policies $\pi_o$ and the termination functions $\beta_o$ differentiable and trains them, together with the policy over options, directly by gradient ascent on the expected return. The intra-option policy gradient and the termination gradient are derived analogues of the ordinary policy gradient, and the key practical result is the termination gradient: an option's termination probability is pushed up where ending the option and switching is advantageous, and pushed down where continuing is. Left alone this collapses options to length one, so a deliberation cost (a small penalty per option switch) is added to keep options temporally extended, which is the regularizer the fun note above anticipated. The option-critic learns the whole hierarchy from reward alone, with no subgoals specified by hand.

Manager sets a direction, worker follows it (FeUdal networks). The feudal view, from Dayan and Hinton's feudal RL (1993) and modernized by Vezhnevets et al.'s FeUdal Networks (FuN, 2017), splits the agent into a slow Manager and a fast Worker. The Manager operates at a coarse time scale and emits a directional subgoal in a learned latent state space (a vector indicating "move the latent state this way"); the Worker is rewarded, by an intrinsic reward, for producing primitive actions that move the latent state in the Manager's chosen direction. The Manager never speaks in primitive actions and the Worker never sees the environment reward directly, so the temporal abstraction is enforced architecturally: the Manager's directional goals persist over a fixed horizon, giving the hierarchy its multiple time scales by construction.

Manager sets a goal state, worker reaches it (goal-conditioned HRL, HIRO). The most directly useful modern recipe is goal-conditioned: a high-level policy proposes a subgoal $g$ (often a target state or a target in a feature space), and a goal-conditioned low-level policy $\pi(a \mid s, g)$ is trained to reach it, rewarded by an intrinsic reward such as the negative distance to $g$. Nachum et al.'s HIRO (2018) made this work off-policy and data-efficiently, with a goal relabeling trick that re-labels the high-level transitions so the high-level critic stays consistent as the low-level policy changes underneath it. Goal-conditioned hierarchies are attractive because the subgoal interface is interpretable (a subgoal is a place to get to) and because the low level can be reused across tasks that share a state space.

Discover skills with no reward at all (unsupervised skill discovery). A fourth family learns a repertoire of options before any task reward exists, by an intrinsic objective that rewards behaviors for being distinguishable. DIAYN (Eysenbach et al., 2018, "Diversity Is All You Need") maximizes the mutual information between a latent skill code and the states the skill visits, so different codes learn to occupy different regions of state space, yielding a set of distinct, reusable skills with no extrinsic reward. The downstream task then only has to learn a policy over these pre-discovered skills, a much shorter-horizon problem. Skill discovery is the unsupervised-representation-learning idea of Chapter 16 transported into the action space: learn a useful basis of behaviors first, solve tasks over that basis second.

Across all four families a single interface recurs: the subgoal as temporal-abstraction boundary. Whether it is an option id, a directional latent vector, a target state, or a skill code, the high level communicates to the low level a commitment that persists for many primitive steps, and that persistence is the temporal abstraction. The design choices, what the subgoal is, how the low level is rewarded for it, how often the high level may change it, are the engineering surface of HRL, and the worked example in Section 5 instantiates the simplest member of the family (a target-cell subgoal with a distance-based intrinsic reward) so the interface is concrete.

4. Temporal Abstraction in Planning and World Models Advanced

Temporal abstraction pays off twice. Section 1 showed its first payoff, a shorter credit-assignment horizon for learning. Its second payoff is for planning, and it is just as large. Recall from Chapter 22 that planning with a model means simulating forward and backing up values; the cost of a planning rollout scales with how many model steps it spans. If the planner can take option-length steps using the option models $R_o$ and $P_o$ of Section 2, then a plan that would have been a thousand primitive-step rollout becomes a handful of option-step rollouts, an exponential reduction in planning depth, with the SMDP discount $\gamma^{\tau}$ handling the variable durations automatically. Abstraction shortens the planning horizon for exactly the reason it shortens the learning horizon: fewer decisions between start and goal.

This is precisely where HRL meets the world models of Chapter 29. A world model is a learned simulator $\hat{P}(s' \mid s, a)$ that lets an agent imagine consequences without acting; a temporally-abstract world model learns the option-level transition $P_o(s' \mid s)$ directly, predicting where an option will land and how much reward it will accrue without rolling out its every primitive step. Planning over such a model is planning over behaviors, and it is what lets methods like Director (previewed in the research-frontier callout) plan in imagination over hundreds of effective steps at acceptable cost. The two ideas are complementary: the world model supplies the simulator, and temporal abstraction supplies the coarse time scale at which simulating is cheap. Chapter 29 develops learned world models and planning in full; the message to carry there is that hierarchy and planning are not separate tricks but the same lever, fewer decisions, applied once to learning and once to search.

5. Worked Example: A Manager-Worker Hierarchy on a Sparse-Reward Gridworld Advanced

We now make the entire section executable on the smallest task that exhibits the long-horizon, sparse-reward difficulty: a gridworld where reward is $+1$ only at a single goal cell far from the start and $0$ everywhere else, with a step budget too short for undirected exploration to stumble onto the goal. We will first show a flat tabular $Q$-learner failing on it, then build a two-level manager-worker hierarchy from scratch that solves it, and finally collapse the hierarchy to a clean, compact version. Code 26.5.1 defines the environment and the flat baseline.

import numpy as np

rng = np.random.default_rng(0)
N = 12                                   # 12x12 grid; goal is far from start -> long horizon
START, GOAL = (0, 0), (N - 1, N - 1)
ACTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]   # up, down, left, right
MAX_STEPS = 80                           # budget; shortest path is 22 steps, but sparse reward

def step(pos, a):
    """One primitive step; stay in place if it would leave the grid."""
    nr, nc = pos[0] + ACTIONS[a][0], pos[1] + ACTIONS[a][1]
    if 0 <= nr < N and 0 <= nc < N:
        pos = (nr, nc)
    r = 1.0 if pos == GOAL else 0.0      # SPARSE: reward only at the goal
    return pos, r, pos == GOAL

def flat_q_learning(episodes=4000, alpha=0.5, gamma=0.97, eps=0.2):
    """Tabular epsilon-greedy Q-learning over PRIMITIVE actions."""
    Q = np.zeros((N, N, 4))
    successes = 0
    for ep in range(episodes):
        pos = START
        for _ in range(MAX_STEPS):
            a = rng.integers(4) if rng.random() < eps else int(np.argmax(Q[pos]))
            nxt, r, done = step(pos, a)
            target = r + (0.0 if done else gamma * np.max(Q[nxt]))
            Q[pos][a] += alpha * (target - Q[pos][a])   # flat one-step TD backup
            pos = nxt
            if done:
                successes += 1
                break
    return successes / episodes

print("flat Q-learning success rate: %.3f" % flat_q_learning())

flat Q-learning success rate: 0.004

The flat agent fails exactly as Section 1 predicted: it cannot learn from a reward it never sees. Now the hierarchy. The worker is a goal-conditioned policy that, given a target cell as a subgoal, learns to reach it under an intrinsic reward (it gets $+1$ for arriving at its subgoal). The manager chooses subgoals, a coarse grid of waypoint cells, with SMDP $Q$-learning over those subgoal choices, bootstrapping with $\gamma^{\tau}$ over the option duration $\tau$ exactly as Section 2 derived. Code 26.5.2 implements both levels from scratch.

# --- WORKER: goal-conditioned Q over (pos, subgoal) with an INTRINSIC reach reward ---
SUBGOALS = [(r, c) for r in range(0, N, 3) for c in range(0, N, 3)] + [GOAL]  # waypoint cells
SG_INDEX = {g: i for i, g in enumerate(SUBGOALS)}

def reach_subgoal(Qw, pos, g, gamma=0.95, eps=0.2, train=True, alpha=0.5, budget=20):
    """Run the worker toward subgoal g; intrinsic reward +1 on reaching g. Returns
    (new_pos, primitive_steps_tau, extrinsic_reward_sum, reached)."""
    gi = SG_INDEX[g]
    tau, ext = 0, 0.0
    for _ in range(budget):
        a = rng.integers(4) if (train and rng.random() < eps) else int(np.argmax(Qw[pos[0], pos[1], gi]))
        nxt, r_ext, _ = step(pos, a)
        ext += r_ext
        reached = (nxt == g)
        r_int = 1.0 if reached else 0.0                      # INTRINSIC: reach the subgoal
        if train:
            tgt = r_int + (0.0 if reached else gamma * np.max(Qw[nxt[0], nxt[1], gi]))
            Qw[pos[0], pos[1], gi, a] += alpha * (tgt - Qw[pos[0], pos[1], gi, a])
        pos = nxt; tau += 1
        if reached:
            break
    return pos, tau, ext, (pos == g)

# --- MANAGER: SMDP Q-learning over subgoal choices, bootstrapping with gamma**tau ---
def manager_worker(episodes=4000, alpha=0.5, gamma=0.97):
    Qm = np.zeros((N, N, len(SUBGOALS)))              # manager value over (pos, subgoal)
    Qw = np.zeros((N, N, len(SUBGOALS), 4))           # worker goal-conditioned value
    successes = 0
    for ep in range(episodes):
        pos, steps = START, 0
        while steps < MAX_STEPS:
            o = rng.integers(len(SUBGOALS)) if rng.random() < 0.2 else int(np.argmax(Qm[pos]))
            g = SUBGOALS[o]
            nxt, tau, ext, _ = reach_subgoal(Qw, pos, g)       # run the option (worker)
            done = (nxt == GOAL)
            G = ext                                            # accumulated extrinsic reward
            tgt = G + (0.0 if done else (gamma ** tau) * np.max(Qm[nxt]))  # SMDP backup: gamma**tau
            Qm[pos[0], pos[1], o] += alpha * (tgt - Qm[pos[0], pos[1], o])
            pos = nxt; steps += tau
            if done:
                successes += 1; break
    return successes / episodes, Qm, Qw

rate, Qm, Qw = manager_worker()
print("manager-worker success rate: %.3f" % rate)

manager-worker success rate: 0.971

The contrast between Output 26.5.1 and Output 26.5.2 is the whole section in two numbers: under one percent flat, ninety-seven percent hierarchical, on the same environment with the same step budget. The hierarchy wins for the two reasons Section 1 named. The worker's intrinsic reward is dense (reaching a nearby waypoint is easy and frequently rewarded), so the low level learns fast. And the manager's SMDP backup with $\gamma^{\tau}$ moves credit across the episode in a handful of option decisions rather than eighty primitive ones, so the sparse goal reward actually reaches the early subgoal choices. Code 26.5.3 distills the same two-level idea into a compact, reusable shape.

def hierarchical_agent(episodes=4000, gamma=0.97):
    """Compact manager-worker: same algorithm, tightened into a reusable loop."""
    Qm = np.zeros((N, N, len(SUBGOALS)))
    Qw = np.zeros((N, N, len(SUBGOALS), 4))
    wins = 0
    for ep in range(episodes):
        pos, steps = START, 0
        while steps < MAX_STEPS:
            o = rng.integers(len(SUBGOALS)) if rng.random() < 0.2 else int(np.argmax(Qm[pos]))
            nxt, tau, ext, _ = reach_subgoal(Qw, pos, SUBGOALS[o])   # option = worker reaching subgoal
            done = nxt == GOAL
            tgt = ext + (0.0 if done else (gamma ** tau) * Qm[nxt].max())  # one SMDP line
            Qm[pos[0], pos[1], o] += 0.5 * (tgt - Qm[pos[0], pos[1], o])
            pos, steps = nxt, steps + tau
            if done:
                wins += 1; break
    return wins / episodes

print("compact hierarchical success rate: %.3f" % hierarchical_agent())

compact hierarchical success rate: 0.969

Read the three code blocks together. Code 26.5.1 established that a flat $Q$-learner cannot solve the sparse-reward task at all. Code 26.5.2 built the manager-worker hierarchy from scratch and solved it, with the worker's dense intrinsic reward and the manager's $\gamma^{\tau}$ SMDP backup doing exactly the work Sections 1 and 2 predicted. Code 26.5.3 compressed the controller to a dozen lines without losing the win. The pedagogical payoff is that temporal abstraction is not exotic: a goal-conditioned worker plus an SMDP backup over subgoals is enough to turn an unsolvable task into a nearly solved one.

import gymnasium as gym
from stable_baselines3 import SAC
from stable_baselines3.her import HerReplayBuffer

# A goal-conditioned worker with Hindsight Experience Replay: the intrinsic
# reach-the-subgoal learning of Code 26.5.2, but relabeling and goal handling are internal.
env = gym.make("FetchReach-v3")                          # dict obs: observation + desired_goal
worker = SAC("MultiInputPolicy", env, replay_buffer_class=HerReplayBuffer,
             replay_buffer_kwargs=dict(n_sampled_goal=4, goal_selection_strategy="future"))
worker.learn(total_timesteps=20_000)                     # learns to reach arbitrary subgoals
# A manager then issues desired_goal vectors and bootstraps with gamma**tau over option length.

We have turned the long-horizon, sparse-reward problem that defeats flat RL into a short-horizon problem by changing the unit of decision from the primitive action to the temporally-extended option, formalized that change as an SMDP with $\gamma^{\tau}$ Bellman backups, surveyed the modern methods that learn the abstraction rather than hand it over, and built a manager-worker hierarchy that solves a task a flat agent never even reaches. The thread that runs through every part of this, fewer decisions between a state and its reward, is the same thread that will run through planning in Chapter 29. Next, Chapter 27 sets reward aside altogether and asks what an agent can learn when it is given a model and a cost (optimal control) or an expert's demonstrations (imitation learning) instead.