← Back to papers
2011 NIPS NeurIPS 2011

Convergent Fitted Value Iteration with Linear Function Approximation

Abstract

Fitted value iteration (FVI) with ordinary least squares regression is known to diverge. We present a new method, "Expansion-Constrained Ordinary Least Squares" (ECOLS), that produces a linear approximation but also guarantees convergence when used with FVI. To ensure convergence, we constrain the least squares regression operator to be a non-expansion in the infinity-norm. We show that the space of function approximators that satisfy this constraint is more rich than the space of "averagers," we prove a minimax property of the ECOLS residual error, and we give an efficient algorithm for computing the coefficients of ECOLS based on constraint generation. We illustrate the algorithmic convergence of FVI with ECOLS in a suite of experiments, and discuss its properties.

🌉 Interdisciplinary Bridge — Machine Learning and Reinforcement Learning
🧭 Keyword Pioneer — fitted value iteration
🐣 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
📈 Trend Setter — Value Iteration

Authors

Daniel J. Lizotte

Topics

Machine Learning > Core Methods > Regression Machine Learning > Optimization & Theory > Optimization Reinforcement Learning > Methods > Deep RL Machine Learning > Learning Types > Reinforcement Learning Reinforcement Learning > Methods > Value Iteration Deep Learning > Learning Types > Reinforcement Learning

Keywords

reinforcement learning function approximation convergence analysis value iteration linear function approximation least squares regression fitted value iteration ecols algorithm linear approximation
Download PDF

Related papers

Co-Training for Domain Adaptation 2011
The Local Rademacher Complexity of Lp-Norm Multiple Kernel Learning 2011
Learning to Agglomerate Superpixel Hierarchies 2011
A Reinforcement Learning Theory for Homeostatic Regulation 2011
A Global Structural EM Algorithm for a Model of Cancer Progression 2011