Abstract: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.
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2605.01339 [cs.LG] |
| (or arXiv:2605.01339v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2605.01339 arXiv-issued DOI via DataCite (pending registration) |
From: Yannik Schnitzer [view email]
[v1]
Sat, 2 May 2026 09:22:05 UTC (3,541 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。