CAREER ADVANCEMENT AWARD: The Complexity of Markov Decision Processes

该项目涉及马尔可夫决策过程(MDP)，并集中于两个问题(1)寻找存在容易实现的最优策略的条件和(2)确定如何识别这些策略。还研究了这些问题的变体，特别是找到了易于实现的策略近似以及识别策略和条件的计算复杂性。这笔赠款将支持从基于数学逻辑的方法向计算机科学(结构复杂性理论)过渡到基于工程应用的方法。正如人工智能中的计算机科学家和离散事件系统中的电气工程师所描述的那样，本提案中重点关注的应用来自规划领域。

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.