Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning

By Richard S. Suttona, Doina Precupb, S. Singha. 1999

Learning, planning, and representing knowledge at multiple levels of temporal abstraction are key, longstanding challenges for AI. In this paper we consider how these challenges can be addressed within the mathematical framework of reinforcement learning and Markov decision processes (MDPs). We extend the usual notion of action in this framework to include options —closed-loop policies for taking action over a period of time. Examples of options include picking up an object, going to lunch, and traveling to a distant city, as well as primitive actions such as muscle twitches and joint torques. Overall, we show that options enable temporally abstract knowledge and action to be included in the reinforcement learning framework in a natural and general way. In particular, we show that options may be used interchangeably with primitive actions in planning methods such as dynamic programming and in learning methods such as Q-learning. Formally, a set of options deﬁned over an MDP constitutes a semi-Markov decision process (SMDP), and the theory of SMDPs provides the foundation for the theory of options. However, the most interesting issues concern the interplay between the underlying MDP and the SMDP and are thus beyond SMDP theory. We present results for three such cases: (1) we show that the results of planning with options can be used during execution to interrupt options and thereby perform even better than planned, (2) we introduce new intra-option methods that are able to learn about an option from fragments of its execution, and (3) we propose a notion of subgoal that can be used to improve the options themselves. All of these results have precursors in the existing literature; the contribution of this paper is to establish them in a simpler and more general setting with fewer changes to the existing reinforcement learning framework. In particular, we show that these results can be obtained without committing to (or ruling out) any particular approach to state

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Active learning of inverse models with intrinsically motivated goal exploration in robots (2013, positive): “We can make an analogy of this formalization with the SemiMarkov Option framework introduced by Sutton [97].”
Value Function Spaces: Skill-Centric State Abstractions for Long-Horizon Reasoning (2021, background): “Our setting is closely related to the options framework of Sutton et al. (1999).”
Skew-Fit: State-Covering Self-Supervised Reinforcement Learning (2019, methodology): “Other prior methods extract reusable skills in the form of latent-variable-conditioned policies, where latent variables can be interpreted as options (Sutton et al., 1999) or abstract skills.”
Exploration from Generalization Mediated by Multiple Controllers (2013, background): “…discussed in the framework of both hierarchical and multitask RL (e.g., Barto and Mahadevan 2003; Botvinick et al. 2009; Caruana 1997; Dayan and Hinton 1993; Dietterich 1998, 2000; Parr and Russell 1998; Ring 1997, 2005; Singh 1992; Sutton et al. 1999; Tanaka and Yamamura 2003; Wilson et al. 2007).”
Using Options and Covariance Testing for Long Horizon Off-Policy Policy Evaluation (2017, methodology): “In particular, we analyze using options-based policies (policies with temporally extended actions) [14] instead of policies over primitive actions.”
A Berkeley View of Systems Challenges for AI (2017, background): “Options have been extensively studied in the context of hierarchical learning [30, 34, 84, 97, 102, 110].”
Curiosity driven reinforcement learning for motion planning on humanoids (2014, background): “Skill learning can be made more explicit by identifying learned skills (Barto et al., 2004) within the option framework (Sutton et al., 1999).”
Hierarchy Through Composition with Multitask LMDPs (2017, methodology): “Like the options framework (Sutton et al., 1999), we build a hierarchy in time.”
Inter-module credit assignment in modular reinforcement learning (2003, background): “In " option " (Sutton, Precup, and Singh 1999) and HAM (Parr and Russell 1997) approaches, modular policies are not learned at all.”