NP-Hardness of checking the unichain condition in average cost MDPs
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 discu...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Elsevier
2012
|
| Online Access: | http://hdl.handle.net/1721.1/69999 https://orcid.org/0000-0003-2658-8239 |