Dyna-Style Planning with Linear Function Approximation and Prioritized Sweeping

By Richard S. Sutton, Csaba Szepesvari, Alborz Geramifard, Michael H. Bowling. 2008

205 citations recorded by the source corpus.

We consider the problem of efficiently learning optimal control policies and value functions over large state spaces in an online setting in which estimates must be available after each interaction with the world. This paper develops an explicitly model-based approach extending the Dyna architecture to linear function approximation. Dyna-style planning proceeds by generating imaginary experience from the world model and then applying model-free reinforcement learning algorithms to the imagined state transitions. Our main results are to prove that linear Dyna-style planning converges to a unique solution independent of the generating distribution, under natural conditions. In the policy evaluation setting, we prove that the limit point is the least-squares (LSTD) solution. An implication of our results is that prioritized-sweeping can be soundly extended to the linear approximation case, backing up to preceding features rather than to preceding states. We introduce two versions of prioritized sweeping with linear Dyna and briefly illustrate their performance empirically on the Mountain Car and Boyan Chain problems.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Reinforcement Learning

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 Computer Vision and Pattern Recognition

In Reinforcement Learning

Citations in the corpus

Value Prediction Network (2017, methodology): “Dyna-Q [32, 34, 39] integrates model-free and modelbased RL by learning an observation-prediction model and using it to generate samples for Q-learning in addition to the model-free samples obtained by acting in the real environment.”
Online Contrastive Divergence with Generative Replay: Experience Replay without Storing Data (2016, methodology): “In contrast to model-based learning approaches, which learn models for the environment (Sutton et al, 2008), OCD GR relies on the underlying RBM, which models only the observed data distribution—a substantially easier problem.”
MOPO: Model-based Offline Policy Optimization (2020, methodology): “While prior approaches have used these models to select actions using planning [67, 17, 54, 51, 59, 70], we choose to build upon Dyna-style approaches that optimize for a policy [64, 66, 73, 32, 26, 28, 44], specifically MBPO [29].”
GenDICE: Generalized Offline Estimation of Stationary Values (2020, methodology): “We mainly focus on the batch RL setting with i.i.d. samples D = [(xi, x′i)] N i=1 ∼ Tp (x, x′), which has been studied by previous authors (e.g., Sutton et al., 2012; Nachum et al., 2019).”
DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections (2019, background): “We discussed in batch learning setting with i.i.d. samples [48].”
Algorithmic Framework for Model-based Deep Reinforcement Learning with Theoretical Guarantees (2018, background): “…Lakshmanan et al., 2015; Hinderer, 2005; Pirotta et al., 2015; 2013), or the linear parametrization of the dynamics, policy, or value function (Abbasi-Yadkori & Szepesvári, 2011; Simchowitz et al., 2018; Dean et al., 2017; Sutton et al., 2012; Tamar et al., 2012), but not much on non-linear models.”
The Effect of Planning Shape on Dyna-style Planning in High-dimensional State Spaces (2018, background): “Dyna was later extended to linear-function approximation so that it could be applied to problems that do not admit an easy tabular state representation (Sutton et al., 2008).”
Learning Powerful Policies by Using Consistent Dynamics Model (2019, methodology): “Extensions of Dyna have been proposed (Silver et al., 2008; Sutton et al., 2012), including deep neural-networks as function approximations.”
Reinforcement learning with misspecified model classes (2013, background): “Model-based (MB) RL techniques have been shown to be more sample-efﬁcient than model-free RL methods [4], [5], [6], [7], making them a natural choice for tackling real-world robotics problems [8].”
Strengths, Weaknesses, and Combinations of Model-based and Model-free Reinforcement Learning (2015, methodology): “Prior work discussed the variations of this idea, as well as their implementations, and showed its effectiveness in practice (Sutton et al., 2008).”
Value-Aware Loss Function for Model-based Reinforcement Learning (2017, methodology): “The learned model is then used to generate new samples, see e.g., [Sutton et al., 2008; Farahmand et al., 2009; Hester and Stone, 2013; Deisenroth et al., 2013, 2015].”
A Deeper Look at Planning as Learning from Replay (2015, methodology): “Note that the graph of linear Dyna contains performance jumps with a size of roughly 100 steps, which corresponds with 1 run out of the 100 runs hitting the 10,000 steps limit.”
Combating the Compounding-Error Problem with a Multi-step Model (2019, background): “Examples of background planning include the Dyna Architecture [Sutton, 1990; Sutton et al. , 2008], or model-based policy-search [Abbeel et al. , 2006; Deisenroth and Rasmussen, 2011; Kurutach et al. , 2018].”
Model-Based Stabilisation of Deep Reinforcement Learning (2018, background): “These conclusions are also in accordance with previous research conducted on linear function approximation in reinforcement learning (Parr et al. 2008; Sutton et al. 2012; Song et al. 2016).”
Planning with Expectation Models (2019, methodology): “For this to be true for linear models, the numerical radius of F needs to be less than 1 [Sutton et al. , 2012].”
Meta-learning of Sequential Strategies (2019, methodology): “More commonly, traditional approaches have used expectation models [Sutton et al., 2012, Schmidhuber, 1990], or deterministic abstract models [Watter et al., 2015, Silver et al., 2016].”