CAREER ADVANCEMENT AWARD: The Complexity of Markov Decision Processes

点击翻译按钮获取中文摘要

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.