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

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

0.00 Avg rating—0 Votes
Article ID: iaor20102886
Volume: 36
Issue: 5
Start Page Number: 527
End Page Number: 530
Publication Date: Sep 2008
Journal: Operations Research Letters
Authors: ,
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.