Data-driven approximate dynamic programming
A linear programming approach
Tobias Sutter (ETH Zürich)
Angeliki Kamoutsi (ETH Zürich)
Peyman Esfahani (TU Delft - Team Bart De Schutter, TU Delft - Support Delft Center for Systems and Control)
John Lygeros (ETH Zürich)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
This article presents an approximation scheme for the infinite-dimensional linear programming formulation of discrete-time Markov control processes via a finite-dimensional convex program, when the dynamics are unknown and learned from data. We derive a probabilistic explicit error bound between the data-driven finite convex program and the original infinite linear program. We further discuss the sample complexity of the error bound which translates to the number of samples required for an a priori approximation accuracy. Our analysis sheds light on the impact of the choice of basis functions for approximating the true value function. Finally, the relevance of the method is illustrated on a truncated LQG problem.