Linear Options

Learning, planning, and representing knowledge in large state spaces at multiple levels of temporal abstraction are key, long-standing challenges for building flexible autonomous agents. The options framework provides a formal mechanism for specifying and learning reusable temporally-extended skills. Although past work has demonstrated the benefit of acting according to options in large state spaces, one of the central advantages of temporal abstraction - the ability to plan using a temporally abstract model - remains a challenging problem when the number of environment states is large or infinite. In this work, we develop a knowledge construct, the linear option, which is capable of modeling temporally abstract dynamics in large state spaces. We show that planning with a linear expectation model of an option's dynamics converges to a fixed point with low Temporal Difference (TD) error. Next, building on recent work on linear feature selection, we show conditions under which a linear feature set is sufficient for accurately representing the value function of an option policy. We extend this result to show conditions under which multiple options may be repeatedly composed to create new options with accurate linear models. Finally, we demonstrate linear option learning and planning algorithms in a simulated robot environment.

Authors

• Jonathan Sorg University of Michigan
• Satinder Singh

Keywords

• Reinforcement Learning
• Temporal Abstraction