Paper Info
Title
Bounds for approximate dynamic programming based on string optimization and curvature
Abstract
In this paper, we will develop a systematic approach to deriving guaranteed bounds for approximate dynamic programming (ADP) schemes in optimal control problems. Our approach is inspired by our recent results on bounding the performance of greedy strategies in optimization of string functions over a finite horizon. The approach is to derive a string-optimization problem, for which the optimal strategy is the optimal control solution and the greedy strategy is the ADP solution. Using this approach, we show that any ADP solution achieves a performance that is at least a factor of β of the performance of the optimal control solution, characterized by Bellman's optimality principle. The factor β depends on the specific ADP scheme, as we will explicitly characterize. To illustrate the applicability of our bounding technique, we present examples of ADP schemes, including the popular rollout method.
Year
DOI
Venue
2014
10.1109/CDC.2014.7040433
CDC
Keywords
Field
DocType
approximate dynamic programming,optimal control,string function optimization,optimal control problems,approximation theory,curvature,bounding technique,string-optimization problem,rollout method,greedy strategies,greedy algorithms,dynamic programming,bellman's optimality principle,string optimization,finite horizon
Dynamic programming,Mathematical optimization,Optimal substructure,Optimality principle,Optimal control,Curvature,Computer science,Greedy algorithm,Stochastic programming,Bounding overwatch
Conference
ISSN
Citations 
PageRank 
0743-1546
0
0.34
References 
Authors
14
4
Name
Order
Citations
PageRank
Yajing Liu131.77
Edwin K. P. Chong21758185.45
Ali Pezeshki345038.31
B. Moran411121.09