semi-Markov decision process (SMDP)

An ordinary MDP ticks like a metronome: every action takes exactly one step. A semi-Markov decision process relaxes that, letting each action take a variable, possibly random amount of time before the next decision is due. Choosing to drive to the airport might occupy forty minutes while checking the mirror takes two seconds, yet both are single decisions the agent commits to and then waits out.

The semi-Markov name signals that the process is Markov at the decision points but not at every instant in between, because how long you dwell matters. Rewards accumulate over the waiting interval and discounting must account for the elapsed time, so the Bellman equations gain an extra term for duration. SMDPs are the natural language for temporal abstraction in RL: the options framework, where an agent picks high-level skills that each run for many low-level steps, is formally an SMDP.