Efficient Learning Algorithms for Problems with Acyclic State Spaces and their Application to Reverse Logistics

该资助为开发适合于无循环状态空间决策问题的方便、定制的机器学习算法提供资金，并将其应用于最优拆卸规划（ODP）的应用领域。所提出的研究的理论框架是基于(i)所考虑的状态空间的非循环性质使得学习过程的动态的明确表征和（ii）一些结果来自被称为排名和选择的统计推断领域。此外，将这些统计结果嵌入所提出的方法框架会产生一些马尔可夫决策过程（MDP）类型的问题，这些问题目前尚未被探索，它们具有一些非常有趣的特殊结构和重要的实际相关性。拟议研究的最后阶段将设法将所得结果应用于ODP问题，并将其纳入目前正在开发的这个问题的计算试验台。预期的理论发展和上述计算测试平台都将通过专门的网站向更广泛的社区开放。如果成功，这项研究的结果将从理论和实践的角度扩展机器学习领域的现有结果。在理论方面，预期的结果将促进利用这些问题的许多子类的特殊结构的可能性，以提高所开发的解决方案的分析可追溯性、效率和严谨性。在实际方面，预期的结果将导致方便的定制学习算法，这些算法具有可证明的已建立的性质，适用于一般具有无循环状态空间的整个决策问题类，特别是ODP问题。最后，通过前一段提到的特殊结构的马尔可夫决策过程的制定和研究，期望在马尔可夫决策过程领域作出更多的贡献；除了在本工作的机器学习环境中出现之外，这些MDP也出现在许多其他应用环境中，这些应用环境涉及具有随机结果的顺序实验的最佳设计。

This grant provides funding for the development of expedient, customized machine learning algorithms that are appropriate for decision problems with acyclic state spaces, and their implementation to the application area of optimal disassembly planning (ODP). The theoretical framework for the proposed research is based on (i) the fact that the acyclic nature of the considered state spaces enables the explicit characterization of the dynamics of the learning process and (ii) some results coming from the area of statistical inference known as ranking & selection". Furthermore, the embedding of these statistical results in the proposed methodological framework gives rise to some Markov Decision Process (MDP)-type of problems, that are currently unexplored and they possess some very interesting special structure and significant practical relevance. The last stage of the proposed research will seek to apply the derived results to the ODP problem, and integrate them in a computational testbed for this problem, that is currently under development. Both, the expected theoretical developments and the aforementioned computational testbed will be accessible to the broader community through a dedicated Website. If successful, the results of this research will extend the currently existing results in the area of machine learning, from both, a theoretical and a practical standpoint. On the theoretical side, the expected results will promote the possibility of exploiting the special structure underlying many sub-classes of these problems, in order to enhance the analytical tractability, efficiency and rigor of the developed solutions. On the practical side, the expected results will lead to expedient customized learning algorithms with provably established properties for the entire class of decision problems with acyclic state spaces, in general, and the ODP problem, in particular. Finally, additional contributions are expected in the area of Markov Decision Processes, through the formulation and study of the specially structured MDP's mentioned in the previous paragraph; beyond their appearance in the machine learning context of this work, these MDP's arise also in many other application contexts that involve the optimal design of sequential experiments with random outcomes.