Limiting Extrapolation in Linear Approximate Value Iteration

Neural Information Processing Systems (NeurIPS)


We study linear approximate value iteration (LAVI) with a generative model. While linear models may accurately represent the optimal value function using a few parameters, several empirical and theoretical studies show the combination of least-squares projection with the Bellman operator may be expansive, thus leading LAVI to amplify errors over iterations and eventually diverge. We introduce an algorithm that approximates value functions by combining Q-values estimated at a set of anchor states. Our algorithm tries to balance the generalization and compactness of linear methods with the small amplification of errors typical of interpolation methods. We prove that if the features at any state can be represented as a convex combination of features at the anchor points, then errors are propagated linearly over iterations (instead of exponentially) and our method achieves a polynomial sample complexity bound in the horizon and the number of anchor points. These findings are confirmed in preliminary simulations in a number of simple problems where a traditional least-square LAVI method diverges.

Related Publications

All Publications

Towards Automated Neural Interaction Discovery for Click-Through Rate Prediction

Qingquan Song, Dehua Cheng, Eric Zhou, Jiyan Yang, Yuandong Tian, Xia Hu

KDD - August 1, 2020

Vid2Game: Controllable Characters Extracted from Real-World Videos

Oran Gafni, Lior Wolf, Yaniv Taigman

ICLR - March 10, 2020

Word-level Speech Recognition with a Letter to Word Encoder

Ronan Collobert, Awni Hannun, Gabriel Synnaeve

ICML - July 13, 2020

Compositionality and Generalization in Emergent Languages

Rahma Chaabouni, Eugene Kharitonov, Diane Bouchacourt, Emmanuel Dupoux, Marco Baroni

ACL - July 4, 2020

To help personalize content, tailor and measure ads, and provide a safer experience, we use cookies. By clicking or navigating the site, you agree to allow our collection of information on and off Facebook through cookies. Learn more, including about available controls: Cookies Policy