Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1143292 | Operations Research Letters | 2007 | 5 Pages |
Abstract
The unichain condition requires that every policy in an MDP result in a single ergodic class, and guarantees that the optimal average cost is independent of the initial state. We show that checking whether the unichain condition fails to hold is an NP-complete problem. We conclude with a brief discussion of the merits of the more general weak accessibility condition.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
John N. Tsitsiklis,