Computational Hardness of Static Distributionally Robust Markov Decision Processes
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914535978303488 |
|---|---|
| author | Li, Yan |
| author_facet | Li, Yan |
| contents | We present some hardness results on finding the optimal policy for the static formulation of distributionally robust Markov decision processes. We construct problem instances such that when the considered policy class is Markovian and non-randomized, finding the optimal policy is NP-hard. When the considered policy class is Markovian and randomized, the robust value function possesses sub-optimal strict local minimizers, and finding the optimal policy is also NP-hard. The considered instances involve an ambiguity set with only two transition kernels. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_02224 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Computational Hardness of Static Distributionally Robust Markov Decision Processes Li, Yan Optimization and Control We present some hardness results on finding the optimal policy for the static formulation of distributionally robust Markov decision processes. We construct problem instances such that when the considered policy class is Markovian and non-randomized, finding the optimal policy is NP-hard. When the considered policy class is Markovian and randomized, the robust value function possesses sub-optimal strict local minimizers, and finding the optimal policy is also NP-hard. The considered instances involve an ambiguity set with only two transition kernels. |
| title | Computational Hardness of Static Distributionally Robust Markov Decision Processes |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2511.02224 |