# Robust Parameter Learning for Uncertain MDPs

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 54 references that are in the map.
- First posted on arXiv 2 May 2026.

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

- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Safety-Constrained Reinforcement Learning for MDPs](https://mlsanity.com/paper/1510.05880/) (2015)
- [PAC Statistical Model Checking for Markov Decision Processes and Stochastic Games](https://mlsanity.com/paper/1905.04403/) (2019)
- [Robust Markov Decision Processes: A Place Where AI and Formal Methods Meet](https://mlsanity.com/paper/2411.11451/) (2024)
- [Robust Anytime Learning of Markov Decision Processes](https://mlsanity.com/paper/2205.15827/) (2022)
- [Parameter Synthesis for Markov Models: Covering the Parameter Space](https://mlsanity.com/paper/1903.07993/) (2019)
- [Sampling-Based Robust Control of Autonomous Systems with Non-Gaussian Noise](https://mlsanity.com/paper/2110.12662/) (2021)
- [Parameter Synthesis for Markov Models: Faster Than Ever](https://mlsanity.com/paper/1602.05113/) (2016)
- [Convex Optimization for Parameter Synthesis in MDPs](https://mlsanity.com/paper/2107.00108/) (2021)
- [Certifiably Robust Policies for Uncertain Parametric Environments](https://mlsanity.com/paper/2408.03093/) (2024)
- [Sequential Convex Programming for the Efficient Verification of Parametric MDPs](https://mlsanity.com/paper/1702.00063/) (2017)
- [Bisimulation Learning](https://mlsanity.com/paper/2405.15723/) (2024)
- [Efficient Sensitivity Analysis for Parametric Robust Markov Chains](https://mlsanity.com/paper/2305.01473/) (2023)
- [Generalized Parameter Lifting: Finer Abstractions for Parametric Markov Chains](https://mlsanity.com/paper/2504.05965/) (2025)
- [Data-Efficient Safe Policy Improvement Using Parametric Structure](https://mlsanity.com/paper/2507.15532/) (2025)
- [Branching Bisimulation Learning](https://mlsanity.com/paper/2504.12246/) (2025)
- [Efficient Solution and Learning of Robust Factored MDPs](https://mlsanity.com/paper/2508.00707/) (2025)

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

- [Bellman-Certified Rounding for Sparse Policy Deployment in MDPs](https://mlsanity.com/paper/2610.00325/) (2026)

## Abstract (arXiv)

Learning-based approaches to verifying unknown Markov decision processes (MDPs) often employ uncertain MDPs. These models use, for example, confidence intervals to capture transition uncertainty and allow synthesis of policies that are robust to this uncertainty. However, this approach typically quantifies uncertainty independently for individual transition probabilities, ignoring dependencies due to shared latent quantities. We propose to learn such models using parametric MDPs (pMDPs), where transition probabilities are expressions over a set of parameters. We project statistical uncertainty from empirical transition frequencies onto the pMDP's parameter space, yielding a probably approximately correct (PAC) uncertainty model for the underlying MDP that respects the algebraic dependencies between transitions. The resulting models are algorithmically challenging to solve, so we propose a hierarchy of sound polytopic outer approximations of the induced confidence set. We implement and evaluate our approach, demonstrating substantially tighter uncertainty estimates than classical interval-based uncertain MDP learning techniques.