semi-Markov options

In an ordinary Markov decision process every decision lasts exactly one timestep. But once your actions are options, a single high-level decision can last a variable, state-dependent number of steps — 'walk to the door' might take three steps in a small room and thirty in a big one. The moment durations stop being fixed, the process the high level sees is no longer a plain MDP; it is a semi-Markov decision process, where time between decisions is itself a random quantity.

The good news is that the core RL machinery survives almost unchanged, you just have to account for elapsed time. The Bellman update over options carries the accumulated discounted reward gathered while the option ran, and discounts the next state's value by gamma raised to the option's actual duration rather than by a single gamma. With that adjustment, value iteration, Q-learning and planning all work over options exactly as they do over primitive actions.

This is the formal reason the options framework is so powerful: by treating extended behaviours as semi-Markov decisions, you get a rigorous calculus for planning at a coarse time scale without giving up any of the convergence guarantees of standard RL. The semi-Markov view is what makes 'options as actions' more than a heuristic.