---
title: "鲁棒马尔可夫决策过程ω-正则目标定量分析新算法"
source: "arXiv AI/CL/LG（论文）"
source_tier: "t2"
url: "https://arxiv.org/abs/2608.25968v1"
permalink: "https://feed.astralor.com/items/itm_8ac7262dc192da9350dc8fe0"
published: "2026-08-26T16:26:13.000Z"
score: 79
channel: "ai"
tags: ["ω-正则目标","奇偶目标","策略迭代","随机博弈","鲁棒MDP"]
---

# 鲁棒马尔可夫决策过程ω-正则目标定量分析新算法

## AI 点评

> 这篇论文把RMDP的定性分析推到定量，是形式化验证方向的一个实质进展。对于研究鲁棒规划、安全强化学习以及自动机验证的读者来说，值得仔细研读。算法上的策略迭代与定性改进结合也很有启发性。

## 速览

该论文研究了线性定义不确定性集合下的(s,a)-矩形鲁棒马尔可夫决策过程（RMDPs）的定量奇偶性分析。作者证明代理和环境均存在纯记忆最优策略，并提出一种结合定量一步改进与定性几乎必然改进的策略迭代算法，实现鲁棒马尔可夫链的多项式时间定量求解。实验表明，该方法比显式归约为随机博弈的现有方法更高效。

## 关键点

- 证明了鲁棒MDP中代理与环境均存在纯记忆最优策略。
- 提出结合定量一步改进与定性几乎必然改进的策略迭代算法。
- 实现线性定义鲁棒马尔可夫链上定量奇偶性的多项式时间求解。
- 实验验证算法优于显式归约为随机博弈的方法。

## 全文

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.

---

引用前请核对原文;本文由星际流动整理:https://feed.astralor.com/items/itm_8ac7262dc192da9350dc8fe0