| Article ID: | iaor20082754 |
| Country: | Netherlands |
| Volume: | 35 |
| Issue: | 3 |
| Start Page Number: | 319 |
| End Page Number: | 323 |
| Publication Date: | May 2007 |
| Journal: | Operations Research Letters |
| Authors: | Tsitsiklis John N. |
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.