CIF: Small: String Submodularity and Near-Optimal Adaptive Control and Sensing

在工程和应用科学中的大量问题中，我们面临着在有限范围内最优地选择一系列行动以最大化一个目标函数的问题。这个问题出现在工程、经济、管理科学和医学的顺序决策中。然而，在这类问题中，最优策略一般很难计算。另一方面，贪婪策略虽然通常不是最优的，但很容易计算，因为它们只涉及在每个阶段找到一个行动，以最大化目标函数中的逐步收益。该研究为贪婪策略相对于最优策略的次最优性提供了一种系统的方法。这项研究在应用领域和教育领域都具有广泛的影响，新的结果将集合上的子模函数的概念扩展到字符串上的子模函数。这些结果表明，在字符串子模数下，贪婪策略的性能不低于序列决策问题中最优策略的(约)63%。在附加的曲率条件下，这个界限变得更加尖锐。这项研究涉及到与这个新的串子模数框架相关的一些问题：1)识别可以使用串子模数框架系统地处理的传感和控制中的典型问题；2)通过将给定的ADP方法归结为与诱导子模串函数相关联的贪婪策略来限制近似动态规划(ADP)的性能；3)通过研究子模数和曲率的宽松定义来超越子模性，以大大扩展该理论的适用范围。

In a great number of problems in engineering and applied science, we are faced with optimally choosing a sequence of actions over a finite horizon to maximize an objective function. The problem arises in sequential decision making in engineering, economics, management science, and medicine. However, in such problems, optimal strategies are hard to compute in general. On the other hand, greedy strategies, though suboptimal in general, are easy to compute because they only involve finding an action at each stage to maximize the step-wise gain in the objective function. This research provides a systematic method to bound the suboptimality of greedy strategies relative to optimal strategies. This research has broad impact both in application areas and educationally.New results extend the notion of submodular functions over sets to submodular functions over strings. These results establish that, under string submodularity, the greedy strategies achieve a performance that is no worse than a factor of (approximately) 63% of optimal strategies in sequential decision problems. Under additional curvature conditions, this bound becomes even sharper. This research involves a number of issues related to this new string-submodularity framework as follows: 1) Identifying canonical problems in sensing and control that can be treated systematically using the string-submodularity framework; 2) Bounding the performance of approximate dynamic programming (ADP) by reducing a given ADP method into a greedy strategy associated with an induced submodular string function; 3) Going beyond submodularity by investigating relaxed definitions of submodularity and curvature in order to greatly expand the scope of the applicability of the theory.