← Back to all posts
Reinforcement LearningSemi-Markov Decision ProcessesSMDPHierarchical RL

Semi-Markov Decision Processes: The Formal Foundation for Temporally-Extended Actions

The mathematical formalism underlying every hierarchical RL method — how SMDPs generalize MDPs to actions with variable, non-unit duration, and how SMDP Q-learning updates values across those variable time gaps — with code and applications in hierarchical RL and continuous-time systems.

O Ohara University · · 10 min read

TL;DR

Every method covered elsewhere on this site assumes actions take exactly one timestep. The Options framework (covered in the companion hierarchical RL article) breaks that assumption by letting a single high-level choice span many primitive steps — and Semi-Markov Decision Processes (SMDPs) are the formal mathematical framework that makes such variable-duration actions rigorous. An SMDP’s Bellman equation accounts explicitly for how much time elapsed during an action, not just which state it led to, which changes how discounting is applied and requires a variant of Q-learning — SMDP Q-learning — adapted specifically for it. This isn’t a competing algorithm family so much as the formal foundation that hierarchical RL, and any system with naturally variable-duration decisions, is built on top of.

MDP vs. SMDP

graph LR
    A[MDP: every action takes 1 step] -->|add variable duration| B[SMDP: actions take tau steps]
    B --> C[Discount by gamma^tau instead of gamma]
    C --> D[Options Framework / Hierarchical RL]

    style D fill:#6366f1,color:#fff

Problem Statement

An ordinary MDP assumes every action takes exactly one discrete timestep, and the discount factor γ is applied uniformly per step. But a temporally-extended action — an “option” like “walk to the door,” which might take 3 steps or 30 depending on the situation — doesn’t fit that assumption. How much should the future be discounted for an action that took 30 steps versus one that took 3? Treating both identically, the way a flat MDP would if you just ignored the difference, throws away real information about elapsed time that matters for correct value estimation.

The SMDP Formalism

An SMDP extends an MDP with an explicit notion of sojourn time — how long an action actually takes to complete — and its Bellman equation discounts by that elapsed time rather than by a fixed single step:

Q(s, o) = E[ r + γ^τ * max_o' Q(s', o') ]

where o is a temporally-extended option (rather than a primitive action), τ is the (possibly random) number of primitive timesteps the option took to complete, and r is the cumulative, appropriately-discounted reward accumulated during the option’s execution, not just a single-step reward.

def smdp_cumulative_reward(rewards_during_option: list[float], gamma: float):
    # Reward accumulated during the option's execution, discounted internally by elapsed steps
    return sum((gamma ** t) * r for t, r in enumerate(rewards_during_option))

SMDP Q-Learning

SMDP Q-learning (Bradtke & Duff, 1994; extended for options by Sutton, Precup, Singh, 1999) adapts the ordinary Q-learning update to account for the option’s actual duration τ when discounting the bootstrapped next-value term:

def smdp_q_learning_update(Q, s, option, cumulative_reward, tau, s_next, alpha=0.1, gamma=0.99):
    bootstrap = (gamma ** tau) * max(Q[s_next].values())   # discount scales with elapsed TIME, not fixed to 1 step
    td_target = cumulative_reward + bootstrap
    td_error = td_target - Q[s][option]
    Q[s][option] += alpha * td_error
    return Q

The key difference from ordinary Q-learning, made explicit here: the discount applied to the bootstrapped next-state value is γ^τ, not a fixed γ. An option that took 10 steps discounts the future far more heavily in a single update than an option that took 1 step — exactly reflecting that more real time, and more opportunity for the environment to have changed, elapsed during the longer option.

How This Connects to the Options Framework

The Options framework covered in the companion hierarchical RL article is, formally, exactly an instance of an SMDP: each option’s initiation set, internal policy, and termination condition together define a temporally-extended action with a random sojourn time τ, and the high-level policy choosing among options is solving precisely the SMDP Bellman equation above. Understanding SMDPs is what makes clear why the Options framework needs a different value-update rule than flat Q-learning — it’s not an arbitrary design choice, it’s a direct mathematical consequence of actions having variable duration.

def option_as_smdp_transition(option, env, state):
    trajectory = option.execute(env, state)   # from the companion hierarchical RL article
    tau = len(trajectory)                      # sojourn time: how many primitive steps the option took
    cumulative_reward = smdp_cumulative_reward([step.reward for step in trajectory], gamma=0.99)
    final_state = trajectory[-1].state
    return cumulative_reward, tau, final_state

Comparison Table

FormalismAction DurationDiscountingUsed By
MDPFixed, always 1 timestepγ per stepStandard Q-learning, actor-critic, most methods on this site
SMDPVariable, random sojourn time τγ^τ, scaled by actual elapsed timeOptions framework, Option-Critic, hierarchical RL generally

Applications

Key Learnings

  1. SMDPs are the “why” behind hierarchical RL’s math, not a separate algorithm to choose between. Every hierarchical RL method that uses temporally-extended actions is implicitly solving an SMDP, whether or not it’s stated in those terms.
  2. Discounting by elapsed time, not by a fixed per-decision factor, is the one specific mathematical change that matters. Everything else about Q-learning carries over essentially unchanged — it’s a small but consequential adjustment to how the future gets discounted.
  3. This formalism predates deep RL by decades, coming out of classical operations research on queueing and maintenance systems — a reminder that a fair amount of modern hierarchical and temporally-extended RL is applying much older mathematical machinery to new, learned function approximators rather than inventing the underlying theory from scratch.

References