# Efficient Solution and Learning of Robust Factored MDPs

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 41 references that are in the map.
- First posted on arXiv 1 Aug 2025.

## Builds on (most cited first, 7 of 7)

- [Robust Adversarial Reinforcement Learning](https://mlsanity.com/paper/1703.02702/) (2017)
- [Solving Robust Markov Decision Processes: Generic, Reliable, Efficient](https://mlsanity.com/paper/2412.10185/) (2024)
- [Scenario-Based Verification of Uncertain Parametric MDPs](https://mlsanity.com/paper/2112.13020/) (2021)
- [Certifiably Robust Policies for Uncertain Parametric Environments](https://mlsanity.com/paper/2408.03093/) (2024)
- [What Are the Odds? Improving the foundations of Statistical Model Checking](https://mlsanity.com/paper/2404.05424/) (2024)
- [Recursive McCormick Linearization of Multilinear Programs](https://mlsanity.com/paper/2207.08955/) (2022)
- [Scalable control synthesis for stochastic systems via structural IMDP abstractions](https://mlsanity.com/paper/2411.11803/) (2024)

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

- [Robust Parameter Learning for Uncertain MDPs](https://mlsanity.com/paper/2605.01339/) (2026)

## Abstract (arXiv)

Robust Markov decision processes (r-MDPs) extend MDPs by explicitly modelling epistemic uncertainty about transition dynamics. Learning r-MDPs from interactions with an unknown environment enables the synthesis of robust policies with provable (PAC) guarantees on performance, but this can require a large number of sample interactions. We propose novel methods for solving and learning r-MDPs based on factored state-space representations that leverage the independence between model uncertainty across system components. Although policy synthesis for factored r-MDPs leads to hard, non-convex optimisation problems, we show how to reformulate these into tractable linear programs. Building on these, we also propose methods to learn factored model representations directly. Our experimental results show that exploiting factored structure can yield dimensional gains in sample efficiency, producing more effective robust policies with tighter performance guarantees than state-of-the-art methods.