options framework

In standard RL, actions are single-step: observe, act, observe again. Options extend this to temporally extended actions. An option like “navigate to the hallway” runs its own internal policy for many steps before terminating and handing control back.

So you’re learning task-specific behaviors / skills – I think this is closely adjacent to Chollet’s program synthesis approach / skill-acquisition-efficiency view on intelligence.

Option (Sutton, Precup & Singh, 1999)

A tuple $(\pi ,\beta )$:
$\pi :\mathcal{S}\times \mathcal{A}\to [0,1]$ … intra-option policy, how to act while the option runs
$\beta :\mathcal{S}\to [0,1]$ … termination condition, probability of stopping in each state

An agent with options learns a policy $\mu :\mathcal{S}\to \mathcal{O}$ over the set of options $\mathcal{O}$ rather than over primitive actions directly.
Once initiated, actions follow $\pi$ until the option terminates stochastically according to $\beta$.

A primitive action is a degenerate option: $\beta (s)=1$ everywhere, terminates after one step.

Because options have variable duration, the resulting decision process is a semi-MDP: transitions take variable amounts of time. The Bellman update generalizes to a multi-step TD target. For an option lasting $\tau$ steps:

$$Q(s_t,o)\leftarrow r_{t+1}+\gamma r_{t+2}+\dots +{\gamma }^{\tau -1}{r}_{t+\tau }+{\gamma }^{\tau }\underset{o^{\prime }}{\max }Q(s_{t+\tau },o^{\prime })$$

The discounted rewards collected while the option ran, plus the discounted value of the state you land in. Same structure as a regular TD update, just spanning $\tau$ steps instead of one. This is model-free: $Q(s,o)$ says how good an option is here, not what it does.

Separate from the option (know-how) is its model (know-what): a prediction of what happens when you run it. Where does it come from? Take an option that walks $s\to s_1\to s_2\to d$ in three steps, collecting rewards $r_1,r_2,r_3$ on the way, with the landing state worth $v(d)$. The return from $s$, grouped into during the option and after it:

$$G=\underset{r(s,o)}{\underbrace{r_1+\gamma r_2+{\gamma }^2{r}_3}}+\underset{p(d\mid s,o)}{\underbrace{{\gamma }^3}}v(d)$$

The grouping is the model: $r(s,o)$ absorbs the rewards collected en route, $p(d\mid s,o)$ absorbs both where the option hands back control and how much of that state’s value survives the delay. In general (random duration $k$, stochastic landing state):

Option model

$r(s,o)=\mathbb{E}\left[r_{t+1}+\gamma r_{t+2}+\dots +{\gamma }^{k-1}{r}_{t+k}\mid S_t=s\right]$ … reward collected while $o$ runs
$p(s^{\prime }\mid s,o)=\mathbb{E}\left[{\gamma }^{k}1(S_{t+k}=s^{\prime })\mid S_t=s\right]$ … probability of terminating in $s^{\prime }$, shrunk by ${\gamma }^k$ for the $k$ steps it took

So $p$ is not a probability distribution: it sums to $\mathbb{E}[{\gamma }^k]\le 1$, and the missing mass is the time cost. With $\gamma =0.9$, an option reaching $d$ in 3 steps has $p(d\mid s,o)={\gamma }^3\approx 0.73$; one needing 40 steps has ${\gamma }^{40}\approx 0.015$, i.e. the landing state is nearly worthless because it lies so far in the future. Duration is encoded inside the transition prediction itself.

That is the point of folding ${\gamma }^k$ into $p$: the Bellman Equation over options keeps the exact one-step form,

$$v(s)=\underset{o}{\max }[r(s,o)+\sum _{s^{\prime }}p(s^{\prime }\mid s,o)v(s^{\prime })]$$

with no $\gamma$ in front of the sum (it’s inside $p$). Any planning algorithm therefore runs unchanged with options in place of actions, each backup jumping a whole behavior instead of one timestep. A primitive action is the $k=1$ case: $r(s,a)=\mathbb{E}[r_{t+1}]$, $p(s^{\prime }\mid s,a)=\gamma \mathrm{Pr}(s^{\prime }\mid s,a)$, recovering the ordinary one-step model.

Models also compose:

$$p(s^{\prime \prime }\mid s,o_1{o}_2)=\sum _{s^{\prime }}p(s^{\prime }\mid s,o_1)p(s^{\prime \prime }\mid s^{\prime },o_2)$$

run $o_1$, land in some intermediate $s^{\prime }$, run $o_2$ from there; the time discounts multiply into ${\gamma }^{k_1+k_2}$ on their own. Composing models means evaluating behavior sequences that were never executed, which is what planning is. And unlike $Q(s,o)$, the transition part is task-independent: where an option lands you stays true whatever the current reward is.

In practice, options are often implemented by expanding the action space. If the original game has $|\mathcal{A}|$ actions and you offer $|\mathcal{T}|$ possible durations, the agent picks from $|\mathcal{A}|\times |\mathcal{T}|$ options (e.g. “move left for 4 steps”, “fire for 1 step”). The intra-option policy is trivial here (repeat the chosen action), but the framework is general: $\pi$ can be an arbitrary policy, like a learned sub-network that handles a whole subtask.

Automatically discovering good options (reusable sub-behaviors that transfer across tasks) is a core problem in hierarchical RL.