A key goal of AI is to create lifelong learning agents that can leverage prior experience to improve performance on later tasks. In reinforcement-learning problems, one way to summarize prior experience for future use is through options, which are temporally extended actions (subpolicies) for how to behave. Options can then be used to potentially accelerate learning in new reinforcement learning tasks. In this work, we provide the ﬁrst formal analysis of the sample complexity, a measure of learning speed, of reinforcement learning with options. This analys is helps shed light on some interesting prior empirical results on when and how options may accelerate learning. We then quantify the beneﬁt of options in reducings ample complexity of a life long learning agent. Finally, the new theoretical insights inspire a novel option-discovery algorithm that aims at minimizing overall sample complexity in lifelong reinforcement learning.