CAREER ADVANCEMENT AWARD: The Complexity of Markov Decision Processes

职业发展奖：马尔可夫决策过程的复杂性

• 批准号: 9610348
• 负责人: Judith Goldsmith
• 金额: $ 5.34万
• 依托单位: University of Kentucky Research Foundation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1997
• 资助国家: 美国
• 起止时间: 1997-07-01 至 2001-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9610348&HistoricalAwards=false
• 关键词: CAREER; ADVANCEMENT; AWARD; Complexity; Markov

This project is concerned with Markov decision processes (MDPs) and concentrates on two problems (1) Finding conditions under which there exist easily implementable optimal policies and (2) Determining how to recognize these policies. Variants on these problems are also studied, in particular finding easily implementable approximations to policies and the computational complexity of recognizing the policies and conditions. This grant will support a transition from a mathematical logic-based approach to computer science (structural complexity theory) to an engineering application-based approach. The applications focussed on in this proposal come from the field of planning, as described both by computer scientists in Artificial Intelligence, and electrical engineers in Discrete Event Systems.

本计画主要研究马尔可夫决策过程（MDP），并集中于两个问题：（1）找出最佳策略存在的条件，以及（2）决定如何辨识这些策略。对这些问题的变体也进行了研究，特别是找到容易实现的近似政策和识别的政策和条件的计算复杂性。 该补助金将支持从基于数学逻辑的方法到计算机科学（结构复杂性理论）的过渡到基于工程应用的方法。 在这个建议中集中的应用程序来自规划领域，正如计算机科学家在人工智能和离散事件系统中的电气工程师所描述的那样。