A General Framework for Bounding Approximate Dynamic Programming Schemes
A General Framework for Bounding Approximate Dynamic Programming Schemes
复制标题
DOI：
10.1109/lcsys.2020.3003477
复制
发表时间：
2018-09
影响因子：
3
通讯作者：
Yajing Liu;E. Chong;A. Pezeshki;Zhenliang Zhang
中科院分区：
文献类型：
--
作者：
Yajing Liu;E. Chong;A. Pezeshki;Zhenliang Zhang
多年来，人们一直对求解动态规划问题的近似方法感兴趣，因为计算以Bellman最优性原理为特征的最优解的固有复杂性。现在存在广泛的近似动态规划（ADP）方法。保证ADP方案的性能至少是最优的某个已知分数，比如说$\beta $，这是非常有趣的。这封信介绍了一个一般的方法来界定ADP方法的性能，在这个意义上说，在随机设置。该方法是基于在字符串优化问题，其中一个必须选择一个字符串（有序集）的行动，以最大限度地提高目标函数的边界贪婪的解决方案的新成果。这种定界技术受到子模块理论的启发，但子模块性并不是建立边界所必需的。相反，边界是基于量化弦函数的曲率的某些概念;曲率越小，边界越好。关键的见解是，任何ADP计划是一个贪婪的计划，一些替代字符串目标函数，符合其最优解和值与原来的最优控制问题。ADP方案然后屈服于上面提到的边界技术，并且代理目标的曲率确定边界的值$\beta $。替代目标及其曲率取决于特定的ADP。
For years, there has been interest in approximation methods for solving dynamic programming problems, because of the inherent complexity in computing optimal solutions characterized by Bellman’s principle of optimality. A wide range of approximate dynamic programming (ADP) methods now exists. It is of great interest to guarantee that the performance of an ADP scheme be at least some known fraction, say $\beta $ , of optimal. This letter introduces a general approach to bounding the performance of ADP methods, in this sense, in the stochastic setting. The approach is based on new results for bounding greedy solutions in string optimization problems, where one has to choose a string (ordered set) of actions to maximize an objective function. This bounding technique is inspired by submodularity theory, but submodularity is not required for establishing bounds. Instead, the bounding is based on quantifying certain notions of curvature of string functions; the smaller the curvatures the better the bound. The key insight is that any ADP scheme is a greedy scheme for some surrogate string objective function that coincides in its optimal solution and value with those of the original optimal control problem. The ADP scheme then yields to the bounding technique mentioned above, and the curvatures of the surrogate objective determine the value $\beta $ of the bound. The surrogate objective and its curvatures depend on the specific ADP.