Is an SMDP just an MDP with missing observations?

No. Its defining extension concerns variable times between decisions, not missing information.

Are options required?

No. Options are a useful temporal-abstraction framework that can induce an SMDP over an underlying MDP.

Must future value use gamma raised to duration?

That is the discrete-time exponential-discount convention used here. Other objectives and time formulations require their own equations.

AI Glossary / Graphs and symbolic AI / Advanced

SMDP

Definition

SMDP stands for semi-Markov decision process: a model for sequential decisions in which the time between decision points can vary. An action can take several underlying time steps or a variable amount of elapsed time before the next decision. The model accounts for the resulting state, rewards, and duration rather than treating every decision as equally spaced.

What it means

A standard discrete-time Markov decision process usually presents one action and one transition at each time step. An SMDP lets a higher-level decision span a longer activity. For example, choosing a docking routine differs from choosing a single motor command: docking may require many commands and may finish at different times.
The word semi does not mean that the model is partly reliable. At decision boundaries, the relevant transition and timing behavior is modeled from the current state and selected action. The state must still contain the information needed for that description. Ignoring relevant history does not become acceptable merely because action durations vary.

How it works

Define the states observed when decisions occur, available activities, and the distribution of their outcomes and durations. Specify when rewards arrive and whether future rewards are discounted by elapsed time. A policy selects an activity at a decision point; the next high-level choice occurs when that activity terminates under the modeled execution scheme.
For a discrete-time discounted example, an activity lasting k steps contributes its discounted rewards during execution plus gamma raised to k times the value of the next state. Options provide one way to construct such activities using an internal policy and termination rule. SMDPs are broader than this particular construction.

Three practical examples

A simulated robot can choose between navigation skills whose completion times depend on the route and obstacles encountered.
A service-workflow model can represent tasks that finish after different durations and lead to different follow-up states.
A game-learning experiment can choose an extended maneuver rather than selecting a fresh high-level strategy after every frame.

Think of it this way

Think of planning a journey by choosing whole train legs rather than deciding separately at every minute. Each leg has a destination and a duration, and arrival creates the next decision opportunity. The analogy is limited because an SMDP explicitly models uncertainty, reward timing, and state information; a timetable alone does not provide all of these.

Worked example

Consider an original deterministic illustration with a discount factor gamma = 0.9 per underlying time step. Both available activities start now and finish in a state assigned continuation value 10. Rewards are received after each step, with the first reward undiscounted in the return measured at the starting decision.
Activity A lasts one step and produces reward 2. Its value is 2 + 0.9 times 10 = 11.
Activity B lasts three steps and produces rewards 1, 1, and 1. Its within-activity return is 1 + 0.9 + 0.81 = 2.71. The continuation value is discounted for three steps: 0.9 cubed times 10 = 7.29. Its total is therefore 10.00. With these stipulated values, A is preferred.
If someone incorrectly used a single factor of 0.9 for B's continuation, they would calculate 2.71 + 9 = 11.71 and reverse the choice. The error comes from treating three elapsed steps as one.
For a further check, let B's duration be one step or three steps, each with probability one-half, with no intermediate rewards and the same continuation value 10. The expected discounted continuation is 0.5 times 9 plus 0.5 times 7.29 = 8.145. Using its mean duration of two gives 0.9 squared times 10 = 8.1, which is different. Discounting a random duration generally requires its distribution, not just its mean.

Illustrative case study

In a fictional warehouse simulation, a team compares a short repositioning skill with a longer route-following skill. An early prototype records only where each skill finishes. The revised simulator also records elapsed steps and rewards received along the way.
The researchers rerun the same scenarios using a stated time-based discount convention and inspect cases where a long skill is interrupted. Their lesson is that temporal abstraction must preserve the timing information relevant to the objective. The scenario illustrates a modeling correction; it does not claim an observed productivity gain or that a particular discount factor is appropriate for real warehouse operations.

Common misconceptions and mistakes

An SMDP does not require every duration to be random; fixed but unequal durations can also be represented. It is not synonymous with partial observability. If hidden conditions matter, they need separate treatment.
Do not add an undiscounted total reward to a discounted continuation without checking the chosen convention. Do not replace a distribution of durations with its average automatically. Finally, a high-level policy can be optimal within an available set of activities without being optimal among every possible sequence of primitive actions.

Business use

The concept helps teams model decisions at a useful operational level while retaining the consequences of time. It is particularly relevant when an activity commits resources until completion and different activities have different durations.
Before comparing policies, agree on what counts as a decision point, whether interruption is possible, and whether the objective is discounted reward, average reward, completion time, or something else. These choices can change the ranking even when the physical activities are identical.

Check your understanding

An activity lasts two steps, gives rewards 2 and 2, then reaches value 5. With gamma = 0.8, what is its return?

Answer: 2 + 0.8 times 2 + 0.8 squared times 5 = 2 + 1.6 + 3.2 = 6.8.

Related terms

Learn next

Next, distinguish the internal policy of an option from the policy that chooses among options. Rework the main example with gamma = 1: A gives 12 and B gives 13 under the stipulated finite calculation. Explain why removing time discounting changes the comparison, and why this does not settle infinite-horizon convergence questions.

Sources

Sutton, Precup and Singh, Between MDPs and semi-MDPs: https://people.eecs.berkeley.edu/~russell/classes/cs294/f05/papers/sutton%2Bal-1999.pdf Sutton, Temporal abstraction lecture slides: https://web.stanford.edu/class/cme241/lecture_slides/rich_sutton_slides/21-temporal-abstraction.pdf AIMA original glossary sentences: https://raw.githubusercontent.com/aimacode/aima-glossary/master/sentences.txt

Previous: Smart data capture Next: Smearing retransformation