# Computational Hardness of Static Distributionally Robust Markov Decision Processes

arXiv: https://arxiv.org/abs/2511.02224 · HTML: https://mlsanity.com/paper/2511.02224/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Nov 2025.

## Built on by (most cited first, 2 of 2)

- [Learning Sequential Decisions from Multiple Sources via Group-Robust Markov Decision Processes](https://mlsanity.com/paper/2602.01825/) (2026)
- [On the Complexity Gap Between POMDPs and Multi-Environment POMDPs](https://mlsanity.com/paper/2610.15010/) (2026)

## Abstract (arXiv)

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.