arXiv cs.AI· Han Bao, Shinsaku Sakaue, Kazuki Watanabe·· 3 天前AI 评分20
基于凸分析视角的 MDP 安全验证查询选择框架
Convex-Analytic View of Query Selection for Safety Verification of Markov Decision Processes
AI 导读
针对 Markov 决策过程安全验证中 Watanabe 和 Unno（2026）提出的失败概率外逼近精化方法，研究者提出统一框架，以显式选定的误差单位度量违反程度：方向得分由外逼近与安全区域之间的支撑函数差除以单位支撑函数归一化。
正文 · 原文
Abstract:Safety verification of a Markov decision process (MDP) asks whether the probabilities of reaching several failure states jointly lie in a convex safe region under every scheduler. Watanabe and Unno (2026) prove safety by refining an outer approximation of the failure probabilities, where each query bounds a nonnegative weighted sum of the probabilities. Their rule selects weights by the largest Euclidean violation. We present a unified framework to measure violation in an explicitly chosen error unit: directions are scored by the support-function gap between the outer approximation and the safe region, normalized by the support function of the unit. We show that the maximal score, when positive, equals the smallest enlargement of the safe region in multiples of that unit that contains the outer approximation. The Euclidean unit recovers the earlier rule; two new rules are generated by the unit cube and the safe region itself. We experimentally evaluate how the choice of measurement rule affects the performance of safety verification for MDPs.
| Subjects: | Optimization and Control (math.OC); Artificial Intelligence (cs.AI); Logic in Computer Science (cs.LO) |
| Cite as: | arXiv:2610.17541 [math.OC] |
| (or arXiv:2610.17541v1 [math.OC] for this version) | |
| https://doi.org/10.48550/arXiv.2610.17541 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Han Bao [view email]
[v1]
Tue, 13 Oct 2026 01:09:51 UTC (26 KB)
来源：arXiv cs.AI · arxiv.org