A Tutorial on Linear Function Approximators for Dynamic Programming and Reinforcement Learning
Abstract
A Markov Decision Process (MDP) is a natural framework for formulating sequential decision-making problems under uncertainty. In recent years, researchers have greatly advanced algorithms for learning and acting in MDPs. This article reviews such algorithms, beginning with well-known dynamic programming methods for solving MDPs such as policy iteration and value iteration, then describes approximate dynamic programming methods such as trajectory based value iteration, and finally moves to reinforcement learning methods such as Q-Learning, SARSA, and least-squares policy iteration. We describe algorithms in a unified framework, giving pseudocode together with memory and iteration complexity analysis for each. Empirical evaluations of these techniques with four representations across four domains, provide insight into how these algorithms perform with various feature sets in terms of running time and performance.
Cite
Text
Geramifard et al. "A Tutorial on Linear Function Approximators for Dynamic Programming and Reinforcement Learning." Foundations and Trends in Machine Learning, 2013. doi:10.1561/2200000042Markdown
[Geramifard et al. "A Tutorial on Linear Function Approximators for Dynamic Programming and Reinforcement Learning." Foundations and Trends in Machine Learning, 2013.](https://mlanthology.org/ftml/2013/geramifard2013ftml-tutorial/) doi:10.1561/2200000042BibTeX
@article{geramifard2013ftml-tutorial,
title = {{A Tutorial on Linear Function Approximators for Dynamic Programming and Reinforcement Learning}},
author = {Geramifard, Alborz and Walsh, Thomas J. and Tellex, Stefanie and Chowdhary, Girish and Roy, Nicholas and How, Jonathan P.},
journal = {Foundations and Trends in Machine Learning},
year = {2013},
pages = {375-451},
doi = {10.1561/2200000042},
volume = {6},
url = {https://mlanthology.org/ftml/2013/geramifard2013ftml-tutorial/}
}