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.