💻 computer science

On the Complexity of Robust Markov Decision Processes and Bisimulation Metrics

This paper investigates the computational complexity of Robust Markov Decision Processes with polytopic uncertainty sets, establishing that the threshold problem is in NP for (s,a)-rectangular cases and in PSPACE for s-rectangular cases, while proving that solving it in polynomial time would resolve the long-standing open question of whether parity games are in P.

Original authors: Marnix Suilen, Guillermo A. Pérez

Published 2026-04-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Marnix Suilen, Guillermo A. Pérez

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are playing a video game where you have to make a series of decisions to collect the most points possible. In a standard version of this game (called a Markov Decision Process, or MDP), the rules are crystal clear. If you press "Jump," you know exactly where you will land and how many points you'll get.

However, in the real world, rules are often fuzzy. Maybe the "Jump" button sometimes lands you in a pit instead of a platform because the game physics are slightly broken or based on shaky data. This is where Robust Markov Decision Processes (RMDPs) come in. Instead of assuming one set of rules, an RMDP assumes there is a whole cloud of possible rulebooks. Your goal isn't just to win; it's to find a strategy that guarantees the best possible score even if the game chooses the worst possible rulebook from that cloud to trick you.

This paper is like a detective report investigating how hard it is to solve these "worst-case" games and how they connect to a different concept called Bisimulation Metrics (which is essentially a way to measure how "similar" two different game states are).

Here is the breakdown of their findings using simple analogies:

1. The Three Types of "Clouds" (Rectangularity)

The authors look at how the "cloud" of possible rules is structured. They found that the shape of this cloud matters a lot for how hard the math is.

The Independent Clouds ( $(s, a)$ -rectangular): Imagine that for every single move you make (like "Jump at the cliff"), the game picks a new, independent rulebook just for that specific moment. It doesn't matter what happened before or what you do next; the game picks a new worst-case scenario for this specific jump.
- The Finding: This is the "easiest" version. The authors proved that if the game is set up this way, we can solve it efficiently (in polynomial time) if the game's "speed" (discount factor) is fixed. It's like solving a puzzle where every piece is independent; you can just look at each piece one by one.
The Linked Clouds ( $s$ -rectangular): Now, imagine the game picks a rulebook for a specific location (state). If you are at "The Cliff," the game picks one rulebook that applies to all your possible jumps from there. The rules for jumping left and jumping right are linked because they come from the same rulebook.
- The Finding: This is much harder. The math gets so complex that it requires a massive amount of computer memory to solve (PSPACE). It's like trying to solve a puzzle where moving one piece changes the shape of three other pieces simultaneously.

2. The "Guess and Check" Game (Complexity)

The paper asks: "Can we quickly decide if there is a strategy that guarantees we get at least 100 points?"

For Independent Clouds: The answer is "Yes, but it's tricky." You can guess a strategy, and if you're right, you can prove it quickly. This puts the problem in a category called NP. It's like a crossword puzzle: it might take a long time to find the answer, but once someone hands you the solution, you can verify it instantly.
The Parity Game Connection: The authors made a shocking discovery. They showed that solving this "worst-case game" is just as hard as solving a famous, decades-old math puzzle called Parity Games.
- Why this matters: Mathematicians have been trying to figure out if Parity Games can be solved quickly for a long time. If someone invents a super-fast algorithm for these Robust Games, they would instantly solve the Parity Game mystery too. It's like finding a master key that opens two different, very famous locked doors.

3. The "Similarity" Connection (Bisimulation Metrics)

The second half of the paper connects these "worst-case" games to measuring similarity.

The Analogy: Imagine you have two robots. You want to know: "If I swap Robot A for Robot B, will the world look different?"
- In the old way, you'd simulate both robots step-by-step and compare their paths. This is slow and clunky.
- The authors discovered that you can turn this "similarity test" into one of those "worst-case games" (RMDPs).
- The Benefit: By turning the similarity test into a game, they could use a powerful tool called Robust Policy Iteration. Think of this as a "smart shortcut." Instead of checking every single possibility one by one (like walking through a maze), the smart shortcut jumps straight to the answer.
- The Result: In their experiments, this "smart shortcut" was 13 to 22 times faster than the standard method for smaller maps. It's the difference between walking across a field and taking a helicopter.

Summary of the "Big Three" Contributions

Speed Limits: They proved that for games with independent rules, we can find the best strategy quickly (if the game speed is fixed), but for games with linked rules, it's a much heavier computational lift.
The Master Key: They showed that solving these games is mathematically equivalent to solving the famous Parity Game problem. If we crack one, we crack the other.
The Shortcut: They showed that using "Robust Policy Iteration" (a method designed for worst-case scenarios) is a much faster way to measure how similar two game states are, compared to the traditional, slower methods.

In a nutshell: This paper maps out the difficulty of planning under uncertainty, links it to some of the hardest unsolved problems in computer science, and accidentally discovers a super-fast way to measure how alike two different scenarios are by treating them as a "worst-case" game.

1. Problem Definition

The paper addresses the computational complexity of Robust Markov Decision Processes (RMDPs).

Context: Standard MDPs assume transition probabilities are known exactly. RMDPs model uncertainty by defining an uncertainty set $U$ containing a family of possible transition functions. The objective is to find a policy that maximizes the expected discounted cumulative reward under the worst-case transition function within $U$ .
Specific Focus: The authors focus on RMDPs where the uncertainty set $U$ is a convex polytope defined in halfspace representation (i.e., $Dx \leq b$ ). This is the standard input format used in practice, distinct from vertex representations.
Decision Problem: The core problem studied is the threshold problem: Given an RMDP and a threshold $\kappa$ , does there exist a policy $\pi$ such that its robust value $V^\pi_M(s_\iota) \geq \kappa$ ?
Rectangularity: The paper distinguishes between two structural assumptions on the uncertainty set:
- $(s, a)$ -rectangular: Uncertainty is independent for each state-action pair. Nature chooses a distribution for each $(s, a)$ independently.
- $s$ -rectangular: Uncertainty is independent per state, but dependent across actions within that state.
- Non-rectangular: General dependencies across the entire system.

2. Methodology

The authors employ a mix of robust optimization theory, complexity theory, and logical encodings to analyze the problem.

Robust Linear Programming (RLP): For $(s, a)$ -rectangular RMDPs, the authors utilize robust linear programming techniques. They show that evaluating a fixed policy can be transformed into a standard Linear Program (LP) by dualizing the infinite constraints imposed by the uncertainty set.
First-Order Theory of the Reals: For the more complex $s$ -rectangular case (where optimal policies may require randomization), the problem is encoded into the first-order theory of the reals. This allows the use of quantifier elimination techniques to establish complexity bounds.
Reductions: The authors establish lower bounds by reducing known hard problems to the RMDP threshold problem:
- Parity Games: Reduced to the RMDP threshold problem.
- Bisimulation Metrics: Reduced to the RMDP threshold problem, establishing a theoretical link between computing distances between MDP states and solving RMDPs.
Algorithmic Construction: They propose a Robust Policy Iteration (RPI) algorithm. This extends standard policy iteration by replacing the policy evaluation step (solving linear equations) with solving the robust LP derived from the uncertainty set.

3. Key Contributions

A. Complexity Results for $(s, a)$ -Rectangular RMDPs

Policy Evaluation: Proved that evaluating a memoryless deterministic policy is in P (Polynomial Time) via robust linear programming.
Threshold Problem: Proved that the decision problem (is there a policy with value $\geq \kappa$ ?) is in NP. This is achieved by guessing a memoryless deterministic policy (which suffices for optimality in this class) and verifying it in polynomial time.
Algorithmic Implication: As a corollary, Robust Policy Iteration is a polynomial-time algorithm for $(s, a)$ -rectangular RMDPs when the discount factor $\gamma$ is fixed.

B. Complexity Results for $s$ -Rectangular RMDPs

Threshold Problem: Proved that for $s$ -rectangular RMDPs (where randomized policies may be optimal), the threshold problem is in PSPACE. This is derived by encoding the existence of an optimal randomized policy and the worst-case transition into the first-order theory of the reals.

C. Lower Bounds and Hardness

P-Hardness: The problem is P-hard, even under rectangularity and convex uncertainty assumptions, as it generalizes standard MDPs.
Parity Game Connection: The authors show that determining the winner of a Parity Game reduces to the RMDP threshold problem. Consequently, finding a polynomial-time algorithm for the general RMDP threshold problem would resolve the long-standing open question of whether Parity Games can be solved in polynomial time.
Bisimulation Metrics: They establish that computing the bisimulation metric between two MDP states is equivalent to solving the robust value problem of a specifically constructed $(s, a)$ -rectangular RMDP.

D. Practical Application: Bisimulation Metrics

The paper demonstrates that Robust Policy Iteration can be used as a practical, efficient algorithm to compute bisimulation metrics between MDP states.
This approach replaces the standard fixed-point iteration (often slow) with robust policy iteration, leveraging the equivalence between the metric's fixed-point equation and the RMDP's robust Bellman equation.

4. Results

Theoretical Results

Complexity Landscape:
- $(s, a)$ -rectangular RMDPs: Threshold problem $\in$ NP.
- $s$ -rectangular RMDPs: Threshold problem $\in$ PSPACE.
- General RMDPs: P-hard (via Parity Games).
Equivalence: The optimal robust value of a constructed RMDP exactly coincides with the bisimulation metric of the original MDP.

Empirical Results

The authors implemented Robust Policy Iteration (RPI) and compared it against Robust Bounded Value Iteration (RBVI) on Frozen Lake environments (5x5, 10x10, 20x20).

Performance: RPI was significantly faster than RBVI.
- On 5x5 maps: RPI was 22x faster.
- On 10x10 maps: RPI was 13x faster.
Optimality Test: Adding an optimality test (RPIOT) further reduced the number of iterations and computation time.
Scalability: On the 20x20 map, RBVI timed out, and RPI ran out of memory (due to solving one massive LP per iteration vs. many small LPs in RBVI), highlighting a trade-off between time efficiency and memory consumption.

5. Significance

Theoretical Advancement: The paper closes a gap in the literature regarding the complexity of RMDPs with polytopic uncertainty in halfspace representation, a format previously open. It clarifies that while $(s, a)$ -rectangular cases are in NP, the general case is likely harder (linked to Parity Games).
Algorithmic Efficiency: It provides a rigorous justification for using Robust Policy Iteration over value iteration for specific classes of RMDPs, offering a polynomial-time solution for fixed discount factors.
Cross-Domain Impact: By linking Bisimulation Metrics to RMDPs, the paper opens a new pathway for computing state distances in MDPs using robust optimization tools. This allows researchers to apply the rich algorithmic toolkit of RMDPs (like policy iteration) to problems in formal verification and model abstraction.
Open Questions: The work highlights that the exact complexity of $(s, a)$ -rectangular RMDPs (whether it is in P) remains an open problem, tied directly to the complexity of Parity Games.

In summary, this paper provides a comprehensive complexity analysis of RMDPs, establishes a novel theoretical connection between robust control and bisimulation metrics, and demonstrates that robust policy iteration is a highly effective practical tool for these problems.