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

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.