Approximate Value Iteration with Temporally Extended Actions

By Timothy A. Mann, Shie Mannor, Doina Precup. 2015

44 citations recorded by the source corpus.

Temporally extended actions have proven useful for reinforcement learning, but their duration also makes them valuable for efficient planning. The options framework provides a concrete way to implement and reason about temporally extended actions. Existing literature has demonstrated the value of planning with options empirically, but there is a lack of theoretical analysis formalizing when planning with options is more efficient than planning with primitive actions. We provide a general analysis of the convergence rate of a popular Approximate Value Iteration (AVI) algorithm called Fitted Value Iteration (FVI) with options. Our analysis reveals that longer duration options and a pessimistic estimate of the value function both lead to faster convergence. Furthermore, options can improve convergence even when they are suboptimal and sparsely distributed throughout the state-space. Next we consider the problem of generating useful options for planning based on a subset of landmark states. This suggests a new algorithm, Landmark-based AVI (LAVI), that represents the value function only at the landmark states. We analyze both FVI and LAVI using the proposed landmark-based options and compare the two algorithms. Our experimental results in three different domains demonstrate the key properties from the analysis. Our theoretical and experimental results demonstrate that options can play an important role in AVI by decreasing approximation error and inducing fast convergence.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

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

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

The Option-Critic Architecture (2016, background): “…but approaches that can be used naturally with continuous state and/or action spaces have only recently started to become feasible (Konidaris et al. 2011; Niekum 2013; Mann, Mannor, and Precup 2015; Mankowitz, Mann, and Mannor 2016; Kulkarni et al. 2016; Vezhnevets et al. 2016; Daniel et al. 2016).”
Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving (2016, background): “All in all, the estimator at every node depends on a value of T which is an order of magnitude smaller than the original 250 steps, which immediately transfers to a smaller variance [21].”
Value Preserving State-Action Abstractions (2020, background): “…Topin et al., 2015), encourage better exploration (Şimşek and Barto, 2004, 2009; Brunskill and Li, 2014; Bacon et al., 2017; Fruit and Lazaric, 2017; Machado et al., 2017; Tiwari and Thomas, 2019; Jinnai et al., 2019), and make planning more efficient (Mann and Mannor, 2014; Mann et al., 2015).”
Options of Interest: Temporal Abstraction with Interest Functions (2020, background): “Constructing such temporal abstractions automatically from data has also been tackled extensively, and with some success (Konidaris et al. 2011; Mann, Mannor, and Precup 2015; Kulkarni et al. 2016; Mankowitz, Mann, and Mannor 2016; Bacon, Harb, and Pre-cup 2017; Machado, Bellemare, and Bowling…”
Flexible Option Learning (2021, background): “This can be beneficial as shorter options are shown to produce better solutions and longer options are preferred for planning [Mann et al., 2015].”
Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning (2020, methodology): “In particular, prior knowledge has been used for problem decomposition (Parr & Russell, 1998; Dietterich, 2000; Mann et al., 2015), data augmentation (Andrychowicz et al., 2017; Pitis et al., 2020), and reward shaping (Ng et al., 1999).”
Learning Abstract Options (2018, background): “Extensive research has focused on discovering these temporal abstractions autonomously [21, 40, 22, 39, 38] while approaches that can be used in continuous state and/or action spaces have only recently became feasible [13, 26, 20, 19, 14, 43, 4].”
When Waiting is not an Option : Learning Options with a Deliberation Cost (2017, background): “For example, options models could be represented by deep networks, necessitating back-and-forth to the GPU, or using a simulator with costly rollouts (Guo et al. 2014; Mann et al. 2015).”
Reinforcement learning for control: Performance, stability, and deep approximators (2018, methodology): “Research on batch RL methods is ongoing, with recent developments in e.g. nonparametric approximation (Farahmand et al., 2016), exploitation of low-level controllers called “op-tions” (Mann et al., 2015), and combinations with deep learning (Lee et al., 2017).”