Article ID Journal Published Year Pages File Type
1142679 Operations Research Letters 2008 4 Pages PDF
Abstract

The Unichain classification problem detects whether a finite state and action MDP is unichain under all deterministic policies. This problem is NPNP-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.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
On polynomial cases of the unichain classification problem for Markov Decision Processes
Authors
, ,