← Back to papers
2006 NIPS NeurIPS 2006

iLSTD: Eligibility Traces and Convergence Analysis

Abstract

We present new theoretical and empirical results with the iLSTD algorithm for policy evaluation in reinforcement learning with linear function approximation. iLSTD is an incremental method for achieving results similar to LSTD, the dataefficient, least-squares version of temporal difference learning, without incurring the full cost of the LSTD computation. LSTD is O(n2 ), where n is the number of parameters in the linear function approximator, while iLSTD is O(n). In this paper, we generalize the previous iLSTD algorithm and present three new results: (1) the first convergence proof for an iLSTD algorithm; (2) an extension to incorporate eligibility traces without changing the asymptotic computational complexity; and (3) the first empirical results with an iLSTD algorithm for a problem (mountain car) with feature vectors large enough (n = 10, 000) to show substantial computational advantages over LSTD.

🚀 Conference Pioneer — NIPS 2006
🌉 Interdisciplinary Bridge — Machine Learning and Reinforcement Learning
📈 Trend Setter — Stochastic Processes
🧭 Keyword Pioneer — temporal difference learning
🐣 Hot Topic Early Bird — reinforcement learning
🐝 Cross-Pollinator — Artificial Intelligence, Computer Science, Computer Vision, Data Science & Analytics, Deep Learning, Healthcare & Medicine, Interdisciplinary, Knowledge & Reasoning, Machine Learning, Mathematics & Optimization, Natural Language Processing, Reinforcement Learning, Robotics

Authors

Alborz Geramifard , Michael Bowling , Martin Zinkevich , Richard S. Sutton

Topics

Machine Learning > Optimization & Theory > Stochastic Processes Reinforcement Learning > Methods > Deep RL Reinforcement Learning > Methods > Policy Learning Machine Learning > Learning Types > Reinforcement Learning Machine Learning > Optimization & Theory > Stochastic Methods

Keywords

reinforcement learning temporal difference learning policy evaluation function approximation convergence analysis linear function approximator linear function approximation eligibility trace
Download PDF

Related papers

Temporal Coding using the Response Properties of Spiking Neurons 2006
Parameter Expanded Variational Bayesian Methods 2006
Effects of Stress and Genotype on Meta-parameter Dynamics in Reinforcement Learning 2006
Ordinal Regression by Extended Binary Classification 2006
Blind source separation for over-determined delayed mixtures 2006