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.
