arXiv:2608.25968cs.AI2026-08

解决不确定环境下的概率性目标最优策略问题,给出高效算法。

Quantitative Analysis of $ω$-Regular Robust MDPs

论文配图:Quantitative Analysis of $ω$-Regular Robust MDPs
图 1 · 摘自论文原文
  • 采用线性约束的不确定性集建模,设计纯记忆无策略最优解。
  • 提出多项式时间算法求解量化公平目标,支持精确概率计算。
  • 适用于需要鲁棒决策的自动化系统,如自动驾驶与安全控制。

鲁棒马尔可夫决策过程(RMDP)通过允许转移概率的不确定性来推广经典MDP,以对抗最坏情况下的环境实现进行优化。本文研究在$(s,a)$-矩形结构下、不确定性集为线性定义的RMDP,聚焦于公平目标(parity objectives),这是ω-正则目标的典型代表。不确定性集是线性定义的,即由关于转移分布的线性不等式及辅助变量构成,涵盖标准的$L_1$和$L_ ty$球以及一般多面体不确定性集。定量值定义为:所有代理策略中,在对抗性环境中仍能保证满足目标的概率上确界。此前工作仅关注定性分析,即判断是否存在单一策略对所有环境策略几乎必然(或正概率)满足目标。本文首次解决了精确的定量问题。主要贡献有三:第一,证明代理与环境均存在纯记忆无策略的最优解;第二,给出针对线性定义鲁棒马尔可夫链的定量公平目标的多项式时间算法,并作为子程序用于RMDP的策略迭代算法,该算法结合了定量一步改进与定性几乎必然改进;第三,实验对比了本方法与显式还原为随机博弈的方法。结果表明,所提方法在效率与精度上具有优势。

原文摘要 · Abstract (English)

Robust Markov Decision Processes (RMDPs) generalize classical MDPs by allowing uncertainty in transition probabilities and optimizing against their worst-case realization. We consider $(s,a)$-rectangular RMDPs with \emph{linearly defined} uncertainty sets and study parity objectives, which are a canonical representation of $ω$-regular objectives. An uncertainty set is linearly defined if it is described by linear inequalities over the transition distribution together with auxiliary variables, which capture the standard $L_1$ and $L_\infty$ balls as well as general polytopic uncertainty sets. The quantitative value is the supremum, over all agent policies, of the satisfaction probability guaranteed against the adversarial environment. Previous work studied the qualitative analysis, namely the almost-sure (resp. positive) problem that asks whether a single agent policy guarantees satisfaction with probability one (resp. positive probability) against every environment policy. In this work, we solve the exact quantitative problem. Our contributions are threefold. First, we show that both the agent and the environment admit pure memoryless optimal policies. Second, we give a polynomial-time algorithm for quantitative parity on linearly defined robust Markov chains and use it as a subroutine in a policy-iteration algorithm for RMDPs. The algorithm combines quantitative one-step improvements with qualitative almost-sure improvements. Finally, we report experiments comparing our approach with the explicit reduction to stochastic games.

强化学习鲁棒决策形式验证

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。