Hierarchical, Symbolic, Language, and Multi-Agent Planning › Skills, options, and temporal abstraction

The single most important idea in this section is that a high-level decision can take time. In the primitive-action MDP formulation from Markov and Partially Observable Decision Processes, each decision epoch selects one primitive action $a_t$. An MDP modeler could encode a macro as an action or augment state with a commitment variable, but the option formalism gives variable-duration closed-loop behavior an explicit interface.

If the agent selects “walk to the door,” the choice must carry both a low-level feedback policy and a rule for returning control. The option formalism supplies those pieces and leads to duration-aware value backups. The standard definition follows Sutton, Precup, and Singh (1999).

Each of the three components answers a different question, and it is worth separating them explicitly. The initiation set answers "when am I allowed to try this?" If the option is "grasp the cup," it makes no sense to start it when the cup is on the other side of the room, so the initiation set excludes those states. The policy answers "what do I actually do while the option is running?" This is the low-level controller, and it can be a hand-written script, a learned neural network, or a classical motion planner. The termination probability answers "when do I stop and reconsider?" A deterministic termination condition is the special case where $\beta$ is either zero or one at every state, which is what you get from a discrete detector such as "the fingers have closed around the cup."

An option is best thought of as a reusable subroutine. "Grasp the cup" is an option whose policy is a learned grasping controller and whose termination is a detector for the fingers closing around the cup. When the option's policy is stochastic, an outcome model must describe terminal state $s'$, duration $\tau$, and cumulative reward. Once you have a small library of such models, a higher-level planner can treat each option as one decision while the option policy handles primitive feedback internally.

The subroutine analogy has a limit. A software subroutine has a specified interface, but its runtime can still depend on inputs and the execution environment. A physical option also evolves through stochastic state transitions, so both its terminal state and its duration can vary. The SMDP equations account for this variable duration explicitly.

Planning over variable-duration options gives a semi-Markov decision process (SMDP) at option decision epochs; one-step options recover the MDP special case. The distinguishing feature of an SMDP is that transitions can have variable duration. Let $\tau$ be the random number of primitive timesteps that option $\omega$ runs before terminating. For the normalized terminal-outcome models in this section, assume the selected option terminates almost surely. Otherwise, its finite-duration outcomes form a subprobability model and nontermination must be handled separately. Write $\Omega(s)=\{\omega:s\in\mathcal I_\omega\}$ for the options eligible to start at $s$. Assume every nonterminal decision state has at least one eligible option; in the displayed backup, take the continuation maximum to be zero if the termination state is terminal. For an eligible $\omega$, its value is the expected discounted return accumulated while it runs, plus the discounted value of the best eligible continuation option once it terminates:

$$\begin{aligned} Q^\star(s, \omega) &= \mathbb{E}\left[ \sum_{k=0}^{\tau-1} \gamma^k r_{t+k+1} + \gamma^\tau \max_{\omega'\in\Omega(s_{t+\tau})} Q^\star(s_{t+\tau}, \omega') \;\middle|\; s_t = s, \omega_t = \omega \right] \\ &= \mathbb{E}\left[ \underbrace{\sum_{k=0}^{\tau-1} \gamma^k r_{t+k+1}}_{\text{discounted reward accrued while option runs}} + \underbrace{\gamma^\tau \max_{\omega'\in\Omega(s_{t+\tau})} Q^\star(s_{t+\tau}, \omega')}_{\text{discounted best eligible continuation value}} \;\middle|\; s_t = s, \omega_t = \omega \right] \end{aligned}$$

where:

• $s$: the state at which the option is initiated
• $\omega$: the eligible option being evaluated (a temporally extended action with $s\in\mathcal I_\omega$)
• $\tau$: the random number of primitive timesteps the option runs before its termination condition triggers
• $t$: the primitive timestep at which the option is initiated, so the option executes at primitive steps $t, t+1, \dots, t+\tau-1$
• $r_{t+k+1}$: the reward received at primitive timestep $t+k+1$, while the option is executing
• $k$: the index over primitive steps within the option, running from $0$ to $\tau-1$
• $\gamma \in [0, 1)$: the discount factor applied to each primitive timestep
• $\gamma^\tau$: the discount applied to the value of the state where the option terminates, scaled by the option's random duration
• $s_{t+\tau}$: the state at which the option terminates and control returns to the high-level planner
• $\omega'$: the continuation option selected at the termination state
• $\max_{\omega'\in\Omega(s_{t+\tau})} Q^\star(s_{t+\tau}, \omega')$: the value of the best eligible option at a nonterminal termination state; the continuation term is zero at a terminal state

The outer expectation is taken over the two random quantities inside the option: the run length $\tau$ (how long the option keeps going before $\beta_\omega$ triggers) and the trajectory of states and rewards encountered while it runs. The expectation is taken under the option's own stochastic process, i.e., the distribution over $(\tau, s_t, s_{t+1}, \dots, s_{t+\tau}, r_{t+1}, \dots, r_{t+\tau})$ induced by following $\pi_\omega$ from $s$ until $\beta_\omega$ triggers, not under the state distribution of the data or under the planner's prior. The sum accumulates the discounted per-step rewards $r_{t+k+1}$ for the $k = 0, 1, \dots, \tau-1$ primitive steps the option actually executes. The second term is the value of the best option available once the option has terminated, discounted by $\gamma^\tau$ so that it is measured in units of the option's initiation time rather than the termination time. Concretely, the reward accrued at primitive step $t+k+1$ is discounted by $\gamma^k$ because it occurs $k$ steps after the option is initiated, and the continuation value at $s_{t+\tau}$ is discounted by $\gamma^\tau$ because the option ran for $\tau$ primitive steps before reaching that state.

The discount exponent is the key difference from a one-step Bellman backup. With the reward indexing above, the immediate reward has exponent zero and the continuation value is multiplied by $\gamma$ because one primitive transition has elapsed. In an SMDP, each internal reward keeps its own offset $k$, while the continuation value is multiplied by $\gamma^\tau$. For $0<\gamma<1$, with otherwise comparable internal rewards and the same positive continuation value, a slower option has a smaller continuation term and is less attractive. At $\gamma=0$, every positive-duration continuation term is zero, so duration creates no preference through that term. For $0<\gamma<1$, a negative common continuation value reverses the continuation-term preference; different intermediate rewards, costs, or terminal values can also reverse the overall preference.

The multiplier $\gamma^\tau$ isolates the attenuation due to duration; it does not by itself determine the option's total return.

The same structure carries over to the state-value function. At a nonterminal state, define $V^\star(s) = \max_{\omega\in\Omega(s)} Q^\star(s, \omega)$; at a terminal state, set $V^\star(s)=0$. The nonterminal optimality equation becomes

$$V^\star(s) = \max_{\omega\in\Omega(s)} \mathbb{E}\left[ \sum_{k=0}^{\tau-1} \gamma^k r_{t+k+1} + \gamma^\tau V^\star(s_{t+\tau}) \;\middle|\; s_t = s, \omega_t = \omega \right],$$

which has the shape of a Bellman optimality equation with a max over eligible options and a duration-aware return. Many dynamic-programming and temporal-difference methods have SMDP counterparts, but the backup must include cumulative option reward, duration, terminal state, and option eligibility. This is more than replacing a one-step transition matrix.

A useful sanity check is to ask what happens when the option library is trivial. Suppose every option is a single primitive action, so that the option's policy picks that action and the termination probability is one at every state. Then $\tau = 1$ with probability one, the sum reduces to the single reward $r_{t+1}$, the discount $\gamma^\tau$ becomes $\gamma$, and the SMDP equation collapses exactly onto the ordinary MDP Bellman equation. The SMDP is therefore a strict generalization: it contains the MDP as the special case where every option is one-step. This containment is the reason we can mix primitive actions and options freely inside a single planner, using primitive actions where fine control matters and options everywhere else.

Planning over options can use dynamic programming on the SMDP. A learned primitive-step model can estimate an option outcome by rolling its closed-loop policy forward, while an option-level model can predict cumulative reward, duration, and terminal state directly. Either route avoids additional real-environment interaction, but neither is free: primitive rollouts accumulate model error and computation, while option-level models introduce their own abstraction and coverage errors.

The equation assumes call-and-return execution: once selected, an option runs until $\beta_\omega$ terminates it. The initiation set controls where an option may start; it does not interrupt an active option. Mid-option reconsideration therefore requires a modified termination rule or a separate polling/interruption mechanism. Termination and interruption rules are design choices because they determine when control returns to the high-level planner.

For model-based planning, define the discounted cumulative option reward $R_\omega = \sum_{k=0}^{\tau-1}\gamma^k r_{t+k+1}$ and model the joint outcome $P(R_\omega,s',\tau\mid s,\omega)$. The state-duration marginal obeys the product rule

$$P(s',\tau=n\mid s,\omega) =P(s'\mid \tau=n,s,\omega)P(\tau=n\mid s,\omega).$$

The conditioning on $\tau=n$ matters because terminal state and duration are usually dependent. Summing over $n$ gives the terminal-state marginal, but discarding duration loses the exponent needed for $\gamma^\tau$. Many value-estimation algorithms admit option-level variants built from this SMDP outcome model; sampling-based planners can likewise search over option outcomes.

The joint model also preserves correlations among reward, duration, and terminal state. A slow option might accrue more reward or reach a better state, so an expected duration and a marginal terminal distribution are not generally enough to reconstruct its value.

There are three practical ways to obtain options, and each teaches a different lesson about world models.

Hand-designed. A human specifies a controller such as pick, place, follow-path, or grip. Hand design can improve inspectability and make intended behavior easier to validate, but it does not guarantee correctness under perception error, implementation bugs, or unmodeled dynamics. Its coverage is limited to the skills and conditions the engineer anticipated.

Discovered from data. Option discovery asks which temporal chunks recur or provide useful control. One family of methods identifies graph bottlenecks: narrow gateways through which many trajectories between regions pass. Another seeks branching or high-control states from which many futures are reachable. These notions are related but not identical. Task-relevant bottlenecks and decision points are useful termination candidates, not a universal rule for where every option should end.

Learned jointly with a high-level policy. One active approach learns skills, termination rules, and the high-level selector together, sometimes using diversity or information objectives. The resulting skills can be useful without corresponding to human concepts, which makes them harder to inspect. This is distinct from the Dreamer family: Dreamer learns latent dynamics and a policy through imagination, but its standard formulation is not an option hierarchy with initiation and termination rules.

Whichever route you take, the planner needs an outcome model for each option: eligibility, cumulative reward, duration, and terminal state. A primitive-step world model can simulate the option policy, while an efficient high-level system may learn or cache an option-level model. The latter changes the model interface and must be validated on the option's execution distribution.

Options shrink the number of high-level decisions but restrict when the high-level policy can switch. The intra-option policy remains closed-loop and may adapt at every primitive step. Under call-and-return execution, however, a different option cannot be selected until termination unless an explicit interruption mechanism is available.

The design tension is: longer options compress more decision epochs but postpone high-level reselection. Reaching, grasping, moving between waypoints, and opening a door are plausible task units. Their boundaries may align with useful symbols, although temporal skills and state abstractions capture different aspects of task structure.

For a deliberately crude full-tree comparison, suppose the primitive horizon is $T$ and each selected option lasts $\bar{\tau}$ steps on average. An option tree then has about $|\Omega|^{T/\bar{\tau}}$ leaves rather than $|\mathcal{A}|^T$. Under these assumptions the option tree is smaller exactly when $|\Omega| < |\mathcal{A}|^{\bar{\tau}}$. Real planners add pruning, state merging, stochastic durations, failures, and unequal option costs; the calculation isolates only branching and depth.

This relationship between horizon and branching factor is easiest to grasp as a pair of growth curves. On a log scale, the primitive cost climbs steeply with horizon while the option cost climbs at a rate set by the mean option duration.