(n_t, \cdot)$. FSCs allow the agent to select actions according to the entire history of past observations [@Meuleau1999], which has been shown to be one of the best approaches for POMDPs [@Lin1992]. [OOIs]{}, our main contribution, make options at least as expressive and as relevant to POMDPs as FSCs, while being able to leverage the hierarchical structure of the problem.

Option-Observation Initiation Sets {#sec:ooi}
==================================

Our main contribution, Option-Observation Initiation Sets ([OOIs]{}), make the initiation sets of options conditional on the option that has just terminated. We prove that [OOIs]{}make options at least as expressive as FSCs (thus suited to POMDPs, see Section \[sec:fsc\]), even if the top-level and option policies are memoryless, while options without [OOIs]{}are strictly less expressive than FSCs (see Section \[sec:vanilla\]). In Section \[sec:experiments\], we show on one robotic and two simulated tasks that [OOIs]{}allow challenging POMDPs to be solved optimally.

Conditioning on Previous Option {#sec:theory}
-------------------------------

Descriptions of partially observable tasks in natural language often contain allusions at sub-tasks that must be sequenced or cycled through, possibly with branches. This is easily mapped to a policy over options (learned by the agent) and sets of options that may or may not follow each other.

A 