On polynomial cases of the unichain classification problem for Markov Decision Processes

详细信息    查看全文

• 作者：Eugene A. Feinberg ; Fenghsu Yang
• 关键词：Markov Decision Process ; Unichain condition ; Recurrent state
• 刊名：Operations Research Letters
• 出版年：2008
• 出版时间：September 2008
• 年：2008
• 卷：36
• 期：5
• 页码：527-530
• 全文大小：519 K

文摘

The Unichain classification problem detects whether a finite state and action MDP is unichain under all deterministic policies. This problem is NP-hard. This paper provides polynomial algorithms for this problem when there is a state that is either recurrent under all deterministic policies or absorbing under some action.