Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Dyna-Style Planning with Linear Function Approximation and Prioritized Sweeping
Richard Sutton, Csaba Szepesvari, Alborz Geramifard, Michael Bowling
Abstract:
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. Dynastyle 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.
Keywords: null
Pages: 528-536
PS Link:
PDF Link: /papers/08/p528-sutton.pdf
BibTex:
@INPROCEEDINGS{Sutton08,
AUTHOR = "Richard Sutton and Csaba Szepesvari and Alborz Geramifard and Michael Bowling",
TITLE = "Dyna-Style Planning with Linear Function Approximation and Prioritized Sweeping",
BOOKTITLE = "Proceedings of the Twenty-Fourth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-08)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2008",
PAGES = "528--536"
}


hosted by DSL   •   site info   •   help