Reinforcement Learning1999intermediate12 min read

Between MDPs and Semi-MDPs — A Framework for Temporal Abstraction in Reinforcement Learning

بين عمليات ماركوف القرارية وشبه الماركوفية — إطار التجريد الزمني في التعلّم المعزَّز

Sutton, R. S. · Precup, D. · Singh, S. — Artificial Intelligence

The problem

Standard treats every action as a single atomic step — "move left", "move right". But real intelligence works at multiple time scales: a chess player thinks in terms of openings and endgame strategies, not individual piece moves. Before this paper, there was no clean mathematical framework that let an RL learn and plan with temporally extended actions while preserving the guarantees of MDPs.

The contribution

The Options Framework: a formal extension of MDPs that introduces options — temporally extended actions defined by three components: an initiation set (where the option can start), an internal (which primitive actions to take), and a termination condition (when to stop). Options generalize both primitive actions (one-step options) and full policies, and the paper proves that standard and learning algorithms — including and — extend naturally to options via semi- theory. The key innovation of intra-option learning allows updating the value of many options simultaneously from a single stream of experience.

The impact

The Options Framework became the foundational formalism for hierarchical reinforcement learning. It directly inspired the option-critic architecture (Bacon et al. 2017) which learns option components end-to-end, and influenced goal-conditioned RL methods like Hindsight Experience Replay (HER). Nearly every hierarchical RL paper since 1999 references this work. The framework bridges the gap between flat RL and structured, human-like planning.

Imagine you're driving across a country. A standard RL agent is like a driver who decides at every intersection — left, right, straight — with no concept of "take the highway to Denver." Each turn is isolated, and planning a cross-country trip requires reasoning about thousands of individual turns.

The Options Framework gives the driver route plans: "Take I-70 West to Denver" is a single option — it has an entry ramp (initiation set), a driving policy (follow the highway signs), and an exit condition (arrive at Denver or run out of fuel). The driver can now plan at the level of highways and cities, not individual intersections, while the highway-driving skill handles the moment-to-moment details.

The problem: flat actions can't scale

In a standard Markov Decision Process, an agent picks one action per time step. This works for simple domains, but in complex environments — a robot navigating a building, a game character completing quests — thousands of primitive steps separate the agent from its goal. Three consequences follow:

Slow learning. The is sparse and delayed. A primitive action at step 1 may not receive credit for a at step 1000.
No reusability. A "go to the door" behavior learned in one task must be re-learned from scratch in another because there is no way to package it as a reusable unit.
Planning explosion. A model-based planner must simulate every single primitive step, making long-horizon planning computationally infeasible.

Open in Lab

Compare three levels: a flat MDP decides every step, an SMDP bundles steps into opaque macro-actions, and the Options Framework sits in between — it can look inside running options and learn from partial executions.

The demo wakes as you arrive…

The core idea: what is an option?

An option is a temporally extended course of action — a reusable skill that bundles multiple primitive steps into one abstract action. Formally, an option $o$ is a triple $\langle \mathcal{I}, \pi, \beta \rangle$ with three components:

Initiation set $\mathcal{I} \subseteq \mathcal{S}$ — the set of states where this option can be activated. Think of it as the "entry ramp": you can only take the highway option if you're near an on-ramp.
Internal policy $\pi: \mathcal{S} \times \mathcal{A} \to [0,1]$ — the option's own decision-making rule. Once activated, this policy selects primitive actions at each step. It's the "driving instructions" for the highway.
Termination condition $\beta: \mathcal{S} \to [0,1]$ — the probability that the option terminates in each . When the option terminates, control returns to the higher-level policy which selects the next option. This is the "exit ramp."

Primitive actions are just special-case options: the initiation set is everywhere, the policy takes exactly one action, and the termination probability is 1 (always stop after one step). So options truly generalize the standard MDP action.

Open in Lab

Explore the three components of an option. Click each component to see how it works in a grid-world example.

The demo wakes as you arrive…

o = \langle \mathcal{I}, \pi, \beta \rangle

The option triple — initiation, policy, termination — 𝓘 = the states where option o is available · π = the closed-loop policy that selects primitive actions while o is active · β = the probability of stopping in each state

Execution model: call and return

How does an agent actually use options? The paper introduces the call-and-return execution model, which works like function calls in programming:

The agent arrives in state $s$ and consults a policy over options $\mu$ to pick an option $o$ .
Option $o$ is "called": its internal policy $\pi$ takes over and selects primitive actions step by step.
After each primitive step lands in a new state $s'$ , the termination function $\beta(s')$ is evaluated. With probability $\beta(s')$ the option terminates and control "returns" to $\mu$ , which selects the next option.

This model is simple and powerful. It creates a natural hierarchy: the high-level policy $\mu$ decides what to do (which skill to invoke), and each option's internal policy $\pi$ decides how to do it (which primitive actions to take). Since primitive actions are themselves options with $\beta = 1$ , the agent can mix abstract skills and fine-grained control seamlessly.

Open in Lab

Watch the call-and-return model in action. The high-level policy picks an option, then the option's internal policy executes until termination.

The demo wakes as you arrive…

The mathematical bridge — semi-MDPs

Why does the paper's title say "between MDPs and semi-MDPs"? Because options transform a standard MDP into something that behaves like a semi-MDP.

In a regular MDP, every transition takes exactly one time step. In a semi-MDP, transitions can take a variable number of steps — the "semi" refers to this relaxation of the fixed-step assumption. When an agent executes an option, the time between decisions varies: a "go to the door" option might take 5 steps, while a "pick up object" option takes 12 steps.

The elegant result is that an MDP with options is mathematically equivalent to a semi-MDP at the level of option selections. This means all the classical SMDP theory — Bellman equations, convergence guarantees, optimal policies — applies directly. No new theory is needed; the existing framework extends naturally.

Bellman equations for options

The standard Q-learning update asks: "what is the value of taking action $a$ in state $s$ ?" With options, the question becomes: "what is the value of starting option $o$ in state $s$ ?" The answer must account for the fact that the option may run for many steps, accumulating discounted rewards along the way, before terminating.

The for the option- $Q(s, o)$ says: the value of starting option $o$ in state $s$ equals the expected sum of discounted rewards collected while $o$ runs, plus the discounted value of the state where $o$ terminates and the best next option is chosen.

Q(s, o) = \mathbb{E}\!\left[\sum_{t=0}^{\tau-1} \gamma^t r_{t+1} + \gamma^\tau \max_{o'} Q(s_\tau, o') \;\middle|\; s_0 = s,\; o_0 = o\right]

Option-value Bellman equation — τ = the random time step at which option o terminates · The sum collects discounted rewards during execution · At termination, the agent picks the best available option

Two ways to learn: SMDP vs. intra-option

The paper presents two approaches to learning option values. Understanding the difference is the key to understanding the paper's most powerful contribution.

SMDP Q-learning treats each option as a black box. It waits for an option to finish, observes the total discounted reward, and updates the option's value. This is correct but wasteful — if the agent runs option A for 20 steps, it learns nothing about options B, C, or D during those 20 steps, even though the experience might be perfectly consistent with what those options would have done.

Intra-option Q-learning looks inside the running option. At every primitive step, it asks: "which other options are consistent with the action just taken?" and updates all of them simultaneously. This is dramatically more sample-efficient because a single stream of experience teaches the agent about many options at once.

Open in Lab

Compare SMDP learning (waits until termination) vs intra-option learning (updates every step). Notice how intra-option learning updates multiple options from one trajectory.

The demo wakes as you arrive…

Q(s, o) \leftarrow Q(s, o) + \alpha \Big[ r + \gamma \Big( (1 - \beta_o(s'))\, Q(s', o) + \beta_o(s')\, \max_{o'} Q(s', o') \Big) - Q(s, o) \Big]

Intra-option Q-learning update rule — At each primitive step: if β(s') ≈ 0 the option continues and we bootstrap from Q(s',o) · if β(s') ≈ 1 the option terminates and we bootstrap from the best next option · the weighting blends both cases smoothly

Read this update rule as a smooth blend between two scenarios. The term $(1 - \beta_o(s'))$ is the probability that option $o$ continues, and $\beta_o(s')$ is the probability it terminates. When the option continues, the agent bootstraps from $Q(s', o)$ — the value of continuing this same option. When it terminates, the agent bootstraps from $\max_{o'} Q(s', o')$ — the value of the best fresh start. The weighted combination handles the stochastic termination naturally.

Option models — planning with skills

Just as learns a model of how primitive actions change the , the options framework defines option models (called multi-time models) that predict the outcome of executing an entire option.

An option model for option $o$ predicts two things from any starting state $s$ :

Where will I end up? A discounted $p_{ss'}^{o}$ giving the probability of landing in state $s'$ after option $o$ terminates, discounted by $\gamma^k$ where $k$ is the number of steps taken.
How much reward will I accumulate? An expected discounted reward $r_s^{o}$ summing the rewards collected during execution.

With these two quantities, the agent can plan at the option level without simulating each primitive step. Instead of "step, step, step... 50 times," it can ask "if I execute go-to-door, where will I be and what reward will I get?" — jumping ahead in a single planning step.

r_s^{o} = \mathbb{E}\!\left[\sum_{k=0}^{\tau-1} \gamma^k\, r_{t+k+1} \;\middle|\; E(o, s, t)\right]

Expected discounted reward of an option model — E(o,s,t) means "option o is initiated in state s at time t" · This compresses the entire option execution into a single predicted reward value

Interruption — improving options without re-learning

A natural question arises: what if the agent discovers a better option halfway through executing the current one? Must it always follow the current option to termination?

The paper proves an interruption theorem: if at any state during an option's execution, the agent can identify a better option (one with higher value), it can safely interrupt the current option and switch — and this will never decrease overall performance.

This result is powerful because it means the agent doesn't need perfectly designed options. Even suboptimal options become useful building blocks: the agent can start executing them and interrupt whenever something better is available. The interruption theorem provides a form of policy improvement at the option level.

The idea in code

Intra-option Q-learning — the core updatepython

Simplified to show the idea — not the real implementation.

import numpy as np

class Option:
    """An option: (initiation_set, policy, termination_fn)."""
    def __init__(self, init_set, policy_fn, beta_fn):
        self.init_set = init_set      # set of states where option can start
        self.policy = policy_fn        # state -> action
        self.beta = beta_fn            # state -> P(terminate)

    def is_available(self, state):
        return state in self.init_set

def intra_option_q_update(Q, s, o_idx, r, s_next, options, alpha, gamma):
    """Update Q-values for ALL consistent options, not just the active one."""
    for i, opt in enumerate(options):
        # Only update options whose policy agrees with the taken action
        if not opt.is_available(s):
            continue
        beta = opt.beta(s_next)
        # Blend: continue vs terminate
        continuation = (1 - beta) * Q[s_next, i]
        termination  = beta * np.max(Q[s_next, :])
        target = r + gamma * (continuation + termination)
        Q[s, i] += alpha * (target - Q[s, i])

# The key insight: one transition (s, a, r, s') updates MANY options,
# not just the one being executed. This is why intra-option learning
# is so much more sample-efficient than SMDP Q-learning.

Options in a grid world

The paper illustrates options with multi-room grid worlds — environments with rooms connected by hallways. Each "go to hallway" option has:

Initiation set: all states within the current room
Internal policy: the shortest path to the target hallway
Termination: stop when reaching the hallway or leaving the room

With just a handful of hallway options plus the primitive actions, the agent can navigate between rooms much faster than with primitive actions alone. The hallway states act as natural subgoals — bottleneck states that connect different regions of the state space.

Open in Lab

Explore a four-room grid world with hallway options. Toggle between flat actions and options to see how temporal abstraction speeds up navigation.

The demo wakes as you arrive…

Why it changed everything

Before the Options Framework, hierarchical RL was a collection of ad-hoc approaches with inconsistent formalisms. This paper unified them under a single mathematical umbrella that was both rigorous and practical.

The framework's impact goes beyond theory. By showing that options are a natural generalization of actions — sitting precisely between the one-step MDP and the variable-step SMDP — it gave the community a shared vocabulary and a set of provably correct algorithms. Subsequent work built directly on these foundations:

1999
The Options Framework (this paper)
Introduced options as the formal bridge between MDPs and semi-MDPs. Proved that Bellman equations and Q-learning extend naturally, and presented intra-option learning.
2000
MAXQ (Dietterich)
Decomposed the value function hierarchically, complementing the options approach with explicit task decomposition trees.
2009
Option discovery via graph methods
Researchers used betweenness centrality and graph Laplacians to automatically identify bottleneck states as option subgoals.
2017
Option-Critic Architecture
Bacon, Harb, and Precup showed how to learn the initiation sets, internal policies, and termination conditions of options end-to-end using policy gradients — no hand-designed subgoals needed.
2018
Hindsight Experience Replay (HER)
Extended ideas of temporal abstraction to goal-conditioned RL. Failed trajectories become successful for alternative goals, echoing the options insight of learning from all consistent behaviors.
2019
HAM and Feudal Networks
Deep hierarchical RL methods combined options-style temporal abstraction with neural network function approximation for complex continuous-control tasks.

CitationSutton, Precup, Singh. Between MDPs and Semi-MDPs — A Framework for Temporal Abstraction in Reinforcement Learning. Artificial Intelligence, 1999.

Terms in this paper

Markov Decision Process (MDP)عملية ماركوف لاتخاذ القرار
Policyالسياسة
Rewardالمكافأة
Discount Factorمُعامل الخصم
Value Functionدالة تقييم العوائد
Action-Value Function (Q-Function)دالة قيمة الفعل المتخذ
Bellman Equationمعادلة بيلمان الرياضية
Q-Learningتعلم دالة الجودة (Q)
Temporal Differenceالفارق الزمني الحسابي
Explorationالاستكشاف (تجربة أفعال جديدة)
Exploitationالاستغلال (اعتماد الأفعال الناجحة)
Episodeجولة تفاعلية كاملة
Trajectoryمسار تتابع الحالات والأفعال
Model-Free RLالتعلم بالتعزيز المباشر (دون نموذج بيئة)
Model-Based RLالتعلم بالتعزيز المعتمد على بناء بيئة