An exact method for analyzing robust Markov decision processes matched the values returned by an explicit stochastic-game baseline on all tested benchmarks. It scaled substantially better on the Garnet and Inventory Management families. Frozen Lake produced the opposite result: at matched sizes, the baseline was roughly an order of magnitude faster and scaled to far larger grids.
The findings are reported in an arXiv v1 preprint dated 26 Aug 2026.
What the method calculates
The study addresses exact quantitative parity analysis for (s,a)-rectangular robust Markov decision processes, or RMDPs, with linearly defined uncertainty sets. Robust Markov chains, or RMCs, are treated as the single-action special case.
From parity to safety
At the center of the approach is an RMC subprocedure that reduces quantitative parity to safety. It first identifies end-components from which the environment can violate parity with probability 1, an almost-sure violation, before carrying out the safety calculation.
That safety calculation is formulated as a linear program, an optimization problem with linear constraints, using a flow-like characterization of reachability probabilities.
Formal results have a boundary
For linearly defined RMCs, safety values and positional environment policies that attain them are computable in polynomial time. The same polynomial-time status is reported for all RMC parity values and optimal positional environment policies.
For parity objectives, both the agent and the environment admit optimal pure memoryless, or positional, policies. A positional policy makes its choice from the current state without relying on a record of earlier choices. The policy-iteration algorithm returns an optimal positional agent policy and its value vector, uses polynomial space, and stops after at most |A||S| calls to Improve.
These guarantees are specific to the stated RMC results; they are not a general polynomial-time result for every linearly defined RMDP. The authors identify polynomial-time exact-value computation as an open question.
The benchmark comparison split in two
The computational comparison used an explicit stochastic-game reduction as a baseline and covered three benchmark classes: Garnet, Inventory Management and Frozen Lake. Garnet and Inventory Management supported both reachability and parity objectives; Frozen Lake supported reachability only.
Each plotted solve-time point was averaged over 10 random seeds, with one-standard-deviation error bars and shaded bands. Runs used a 120-second timeout. Raw numerical times, exact configuration counts and complete size ranges are not reported in the supplied analysis, so the results are best read as scaling patterns rather than a precise speed ranking at every size.
On Garnet and Inventory Management, the proposed algorithm scaled substantially better than the baseline across both uncertainty norms and both objectives. On Inventory Management, it solved instances up to approximately 1,200 states; the baseline exceeded the timeout at a few hundred states and was about one to two orders of magnitude slower at the largest matched sizes.
The authors interpret the proposed method as more efficient and scalable when branching factors are large. Frozen Lake had a fixed small branching factor. There, the baseline was roughly an order of magnitude faster at matched sizes and scaled to far larger grids.
The paper also says the baseline is faster when uncertainty sets have few extreme points. The performance picture was therefore mixed: the proposed method scaled better on Garnet and Inventory Management, while the baseline was faster and scaled farther on Frozen Lake.
A result shaped by model structure
Observed policy-iteration counts for both methods were below the theoretical worst-case bound, which is exponential in the number of states. The reviewed material does not give the numerical iteration counts, so the observation describes the tested runs rather than the worst case.
The empirical evidence remains limited to the three computational families used in the comparison. The values matched across all tested benchmarks, but the speed result changed with the family: two favored the proposed method's scaling, while Frozen Lake favored the baseline.
Taken together, the preprint describes an exact framework with a benchmark-dependent speed profile. Its value agreement held across the reported tests, while its practical advantage was concentrated on Garnet and Inventory Management rather than Frozen Lake. Broader claims about other models or solvers would require further testing.
Paper data and sources
Original title: Quantitative Analysis of $ω$-Regular Robust MDPs
Authors: Ali Asadi, Krishnendu Chatterjee, Ehsan Kafshdar Goharshady et al.
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-26
DOI: Not available
Original paper · Full text