鲁棒平均奖励马尔可夫决策过程：通过插入式归约实现极小极大最优学习

# 基于插入约简的极小极大最优学习 来源：https://arxiv.org/html/2608.06545 ## 鲁棒平均奖励马尔可夫决策过程：基于插入约简的极小极大最优学习 Yuepeng Yang Yale & Penn 耶鲁大学统计与数据科学系。宾夕法尼亚大学沃顿商学院统计与数据科学系。Yuejie Chi11footnotemark:1 Yale (2026年8月5日) ###### 摘要 分布鲁棒马尔可夫决策过程为模型不确定性下的序贯决策提供了原则性框架。我们研究在平均奖励准则下，学习一个ε\\varepsilon\-最优鲁棒策略需要多少样本是必要且充分的。生成模型从名义转移核中提供样本，而策略性能则在半径为至多σ\\sigma的\\((s,a)\\)\\((s,a)\\)\-矩形全变差不确定集下进行评估。令\\(H\_0\\)\\(H\_\{0\}\\)和\\(H\_\\sigma\\)\\(H\_\{\\sigma\}\\)分别表示名义与鲁棒最优偏差跨度。我们将\\(\\sigma H\_0\\)\\(\\sigma H\_\{0\}\\)确定为区分高容差与低容差机制的扰动尺度。我们的匹配上界与下界表明，在忽略对数因子的情况下，极小极大总样本复杂度为 \\[NSA\\asymp\\frac\{SA\}\{\\varepsilon^\{2\}\}\\cdot\\begin\{cases\}\\min\\\{H\_\{0\},H\_\{\\sigma\}\\\},&\\varepsilon\\gtrsim\\sigma H\_\{0\}\\\\\[2.84526pt\] \\min\\\{H\_\{0\},H\_\{\\sigma\}\\\}\+\\sigma H\_\{\\sigma\}^\{2\},&\\varepsilon\\lesssim\\sigma H\_\{0\}\\end\{cases\},\\] 其中\\(S\\)\\(S\\)和\\(A\\)\\(A\\)分别是状态数和动作数，\\(N\\)\\(N\\)是每个状态-动作对的样本数。样本复杂度由一个类似于名义AMDP结果的线性跨度项和一个仅在低容差机制中出现的鲁棒性特定项组成。我们通过基于约简的插入式程序达到这些速率，该程序选择约简方式——名义或鲁棒——及其折扣因子：一个利用已知跨度参数进行这些选择的跨度知情程序，以及一个从数据中校准这两个选择的跨度不可知程序。 ## 1 引言 强化学习 \(RL\)（Sutton和Barto，2018 (https://arxiv.org/html/2608.06545#bib.bib88)）作为不确定性下序贯决策的范式，使智能体能够通过与环境的交互来学习最优行为。强化学习已在机器人技术（Mnihet al.，2015 (https://arxiv.org/html/2608.06545#bib.bib24)；Koberet al.，2013 (https://arxiv.org/html/2608.06545#bib.bib23)）、博弈（Silveret al.，2016 (https://arxiv.org/html/2608.06545#bib.bib25)）和生成式AI（Guoet al.，2025 (https://arxiv.org/html/2608.06545#bib.bib45)）等领域取得了成功的应用。支撑强化学习的一个流行模型是马尔可夫决策过程（MDP），其中智能体的目标是在环境中学习一个最大化某种形式的聚合期望奖励的策略。常见的聚合方式包括有限时域上的总奖励和无限时域上的折扣奖励之和。尽管这些方式很流行，但它们可能不太适合连续学习任务（Naiket al.，2019 (https://arxiv.org/html/2608.06545#bib.bib843)）。在本研究中，我们关注长期平均奖励： \\[\\rho^\{\\pi\}\(s\):=\\lim\_\{T\\rightarrow\\infty\}\\mathbb\{E\}\_\{P^\{0\}\}^\{\\pi\}\\left\[\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}r\(s\_\{t\},a\_\{t\}\)\\mid s\_\{0\}=s\\right\],\\] 它通过评估当步数趋于无穷时每个时间步所获得的期望奖励来刻画策略的稳态性能。这里，\\(r\(s\_t,a\_t\)\\)\\(r\(s\_\{t\},a\_\{t\}\)\\)是智能体根据策略\\(\\pi\\)\\(\\pi\\)在状态\\(s\_t\\)\\(s\_\{t\}\\)下选择动作\\(a\_t\\)\\(a\_\{t\}\\)时在时间步\\(t\\)\\(t\\)获得的即时奖励，期望值是在给定初始状态\\(s\_0=s\\)\\(s\_\{0\}=s\\)的情况下，根据转移核\\(P^0\\)\\(P^\{0\}\\)和策略\\(\\pi\\)\\(\\pi\\)对轨迹的随机性取的。与优先考虑早期奖励的折扣设置不同，该指标寻求一个在所有状态下最大化一致长期收益的策略。标准强化学习中的一个重大挑战是对固定概率核的依赖。在一个环境中学习的策略在另一个环境中可能无效，即使变化很小（Rameshet al.，2024 (https://arxiv.org/html/2608.06545#bib.bib26)；Sinhaet al.，2020 (https://arxiv.org/html/2608.06545#bib.bib27)）。解决此问题的一种流行方法是考虑分布鲁棒优化（DRO）框架，其中环境的概率分布允许在规定的置信集内变化，而不是固定的（Mohajerin Esfahani和Kuhn，2018 (https://arxiv.org/html/2608.06545#bib.bib31)；Wiesemannet al.，2014 (https://arxiv.org/html/2608.06545#bib.bib32)；Goh和Sim，2010 (https://arxiv.org/html/2608.06545#bib.bib33)；Duchi和Namkoong，2021 (https://arxiv.org/html/2608.06545#bib.bib34)）。在马尔可夫决策过程的背景下，转移不确定性早已通过鲁棒和分布鲁棒公式进行研究（Iyengar，2005 (https://arxiv.org/html/2608.06545#bib.bib887)；Nilim和El Ghaoui，2005 (https://arxiv.org/html/2608.06545#bib.bib865)；Xu和Mannor，2012 (https://arxiv.org/html/2608.06545#bib.bib22)；Wiesemannet al.，2013 (https://arxiv.org/html/2608.06545#bib.bib907)）。与我们的设置更直接相关的是，分布鲁棒平均奖励MDP（AMDP）将转移核建模为属于指定的不确定集\\(\\mathcal\{P\}\\)\\(\\mathcal\{P\}\\)（Wanget al.，2023b (https://arxiv.org/html/2608.06545#bib.bib35),a (https://arxiv.org/html/2608.06545#bib.bib36)）。在此框架下，我们寻求一个在该集合内的最坏情况情景下有效的策略，定义为鲁棒平均奖励： \\[\\rho\_\{\\mathcal\{P\}\}^\{\\pi\}\(s\):=\\min\_\{P\\in\\mathcal\{P\}\}\\lim\_\{T\\rightarrow\\infty\}\\mathbb\{E\}\_\{P\}^\{\\pi\}\\left\[\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}r\(s\_\{t\},a\_\{t\}\)\\mid s\_\{0\}=s\\right\].\\] 通过针对这种最悲观的模型进行优化，我们有助于确保即使环境动态不确定，智能体的性能也能保持可靠。本文研究生成模型设置下分布鲁棒性的统计代价，其中算法可以访问一个模拟器，该模拟器从名义转移核\\(P^0\\)\\(P^\{0\}\\)为每个状态-动作对生成\\(N\\)\\(N\\)个独立样本。同时，性能通过围绕\\(P^0\\)\\(P^\{0\}\\)的矩形全变差不确定集上的鲁棒平均奖励来评估。在此框架内，一个关键的统计问题是：*获得一个在鲁棒平均奖励下ε\\varepsilon\-最优的策略需要多少样本是必要且充分的？* 研究平均奖励MDP样本复杂性的一个关键问题参数是最优偏差跨度。它通过衡量瞬态奖励相对于长期平均在初始状态间的变化程度来量化平均奖励MDP的动态范围。已知名义平均奖励MDP具有极小极大最优样本复杂度\\(\\widetilde\{O\}\(SAH\_\{0\}\\varepsilon^\{\-2\}\)\\)\\(\\widetilde\{O\}\(SAH\_\{0\}\\varepsilon^\{\-2\}\)\\)（Wanget al.，2022 (https://arxiv.org/html/2608.06545#bib.bib4)；Zurek和Chen，2024 (https://arxiv.org/html/2608.06545#bib.bib5)），其中\\(H\_0\\)\\(H\_\{0\}\\)是名义最优偏差跨度。在鲁棒设置中，最近的工作为该问题建立了上界。Rochet al. (2025 (https://arxiv.org/html/2608.06545#bib.bib8)) 开发了从鲁棒AMDP到鲁棒折扣MDP的约简，而Rochet al. (2026 (https://arxiv.org/html/2608.06545#bib.bib9)) 提出了鲁棒Halpern迭代的无参数变体。其保证分别依赖于相应论文中定义的鲁棒跨度参数\\(H\_\{\\mathrm\{Roch\}\}\\)\\(H\_\{\\mathrm\{Roch\}\}\\)和\\(H\_\{\\mathrm\{RHI\}\}\\)\\(H\_\{\\mathrm\{RHI\}\}\\)的二次方，样本复杂度为\\(\\widetilde\{O\}\(SAH\_\{\\mathrm\{Roch\}\}^\{2\}\\varepsilon^\{\-2\}\)\\)\\(\\widetilde\{O\}\(SAH\_\{\\mathrm\{Roch\}\}^\{2\}\\varepsilon^\{\-2\}\)\\)和\\(\\widetilde\{O\}\(SAH\_\{\\mathrm\{RHI\}\}^\{2\}\\varepsilon^\{\-2\}\)\\)\\(\\widetilde\{O\}\(SAH\_\{\\mathrm\{RHI\}\}^\{2\}\\varepsilon^\{\-2\}\)\\)。名义AMDP的极小极大理论与现有鲁棒上界之间的对比使得我们的主要统计问题在很大程度上仍未解决。 ### 1.1 我们的贡献 我们刻画了极小极大样本复杂度，并开发了能达到该复杂度的基于约简的程序。对于半径至多为\\(\\sigma\\)\\(\\sigma\\)的\\((s,a)\\)\\((s,a)\\)\-矩形全变差不确定集，我们的匹配上下界将极小极大样本复杂度（在忽略对数因子的情况下）刻画为 \\[NSA\\asymp\\frac\{SA\}\{\\varepsilon^\{2\}\}\\begin\{cases\}\\min\\\{H\_\{0\},H\_\{\\sigma\}\\\},&\\varepsilon\\gtrsim\\sigma H\_\{0\},\\\\\[2.84526pt\] \\min\\\{H\_\{0\},H\_\{\\sigma\}\\\}\+\\sigma H\_\{\\sigma\}^\{2\},&\\varepsilon\\lesssim\\sigma H\_\{0\}.\\end\{cases\}\(1\)\\] 这里，\\(H\_0\\)\\(H\_\{0\}\\)和\\(H\_\\sigma\\)\\(H\_\{\\sigma\}\\)分别是名义和鲁棒跨度参数。两个参数都至少为1，且一般而言两者互不控制：命题1 (https://arxiv.org/html/2608.06545#Thmproposition1) 表明，对于任意固定的\\(\\sigma\>0\\)\\(\\sigma\>0\\)，任何规定的对\\((H\_0,H\_\\sigma)\\)\\((H\_\{0\},H\_\{\\sigma\}\\)\\)都可以实现。 ##### 高容差和低容差机制。在命题2 (https://arxiv.org/html/2608.06545#Thmproposition2)中，我们证明最优鲁棒平均奖励至多比名义最优平均奖励小\\(\\sigma H\_0\\)\\(\\sigma H\_\{0\}\\)。将此扰动尺度与目标容差\\(\\varepsilon\\)\\(\\varepsilon\\)进行比较，将鲁棒学习分为两种机制。在*高容差机制*\\(\\sigma H\_0\\lesssim\\varepsilon\\)\\(\\sigma H\_\{0\}\\lesssim\\varepsilon\\)中，求解名义AMDP以标准速率\\(\\widetilde\{O\}\(SAH\_\{0\}\\varepsilon^\{\-2\}\)\\)\\(\\widetilde\{O\}\(SAH\_\{0\}\\varepsilon^\{\-2\}\)\\)实现鲁棒ε\\varepsilon\-最优性。此外，当\\(H\_\\sigma\\leq H\_0\\)\\(H\_\{\\sigma\}\\leq H\_\{0\}\\)时使用鲁棒约简可将其改进为\\(\\widetilde\{O\}\(SAH\_\\sigma\\varepsilon^\{\-2\}\)\\)\\(\\widetilde\{O\}\(SAH\_\{\\sigma\}\\varepsilon^\{\-2\}\)\\)。然而，在*低容差机制*\\(\\varepsilon\\lesssim\\sigma H\_0\\)\\(\\varepsilon\\lesssim\\sigma H\_\{0\}\\)中，必须考虑扰动。表1 (https://arxiv.org/html/2608.06545#S1.T1) 总结了在\\(H\_0\\)\\(H\_\{0\}\\)和\\(H\_\\sigma\\)\\(H\_\{\\sigma\}\\)的两种排序下的这些机制。 表 1：极小极大最优样本复杂度的四机制总结，忽略对数因子。虚线轮廓标记使用鲁棒约简的机制。跨度排序 | 高容差 \\(\\sigma H\_0\\lesssim\\varepsilon\\)\\(\\sigma H\_\{0\}\\lesssim\\varepsilon\\) | 低容差 \\(\\varepsilon\\lesssim\\sigma H\_0\\)\\(\\varepsilon\\lesssim\\sigma H\_\{0\}\\) ---------|------|------ \\(H\_\\sigma\\leq H\_0\\)\\(H\_\{\\sigma\}\\leq H\_\{0\}\\) | \\(\\dfrac\{SAH\_\{\\sigma\}\}\{\\varepsilon^\{2\}\}\\)\\(\\dfrac\{SAH\_\{\\sigma\}\}\{\\varepsilon^\{2\}\}\\) | \\(\\dfrac\{SA\(H\_\{\\sigma\}\+\\sigma H\_\{\\sigma\}^\{2\}\)\}\{\\varepsilon^\{2\}\}\\)\\(\\dfrac\{SA\(H\_\{\\sigma\}\+\\sigma H\_\{\\sigma\}^\{2\}\)\}\{\\varepsilon^\{2\}\}\\) \\(H\_0\\leq H\_\\sigma\\)\\(H\_\{0\}\\leq H\_\{\\sigma\}\\) | \\(\\dfrac\{SAH\_\{0\}\}\{\\varepsilon^\{2\}\}\\)\\(\\dfrac\{SAH\_\{0\}\}\{\\varepsilon^\{2\}\}\\) | \\(\\dfrac\{SA\(H\_\{0\}\+\\sigma H\_\{\\sigma\}^\{2\}\)\}\{\\varepsilon^\{2\}\}\\)\\(\\dfrac\{SA\(H\_\{0\}\+\\sigma H\_\{\\sigma\}^\{2\}\)\}\{\\varepsilon^\{2\}\}\\) 我们使用约简方法来获得这些结果。我们表明，鲁棒AMDP可以约简为名义AMDP或鲁棒折扣MDP，而后者又可以进一步处理。这一见解将鲁棒平均奖励学习简化为更简单的构造块。我们的算法——跨度知情程序（算法1）和跨度不可知程序（算法2）——是不同的：跨度知情程序利用跨度参数的知识来选择约简方式和折扣因子；跨度不可知程序从数据中估计这些量，而无需先验知识。与显式建模鲁棒偏差函数的现有方法不同，我们的程序通过基本的近似动态规划步骤运行。 从技术角度看，我们的分析通过以下关键步骤弥合名义和鲁棒AMDP之间的差距： —— *从一个核转移到另一个核的跨度稳定性*。我们建立了一个一般的灵敏度结果（引理3），它控制了当转移核变化时最优偏差跨度的变化。该工具使得我们能够将约简生成的折扣问题的解转换为鲁棒AMDP的解。 —— *接近最优策略的鲁棒性*。我们展示了通过充分优地求解适当的约简问题而获得的策略是鲁棒最优的，并且我们建立了在最优策略的邻域内鲁棒偏差函数的H\\-稳定性。 —— *信息论下界*。我们构造了一个硬实例族（命题7），并证明了任何算法要获得鲁棒ε\\varepsilon\-最优策略所需的样本数量的下界。该构造基于最小化问题和估计问题的紧密联系。 在高层次上，我们的算法流程如图1 (https://arxiv.org/html/2608.06545#S1.F1)所示。 图 1：算法概览。虚线框内的操作需要跨度知识；跨度不可知程序从数据中估计这些量。 ### 1.2 相关工作 …（此处省略，原文未给出） ### 1.3 符号约定 对于正整数\\(d\\)\\(d\\)，令\\(\\Delta\(\\mathcal\{S\}\)\\)\\(\\Delta\(\\mathcal\{S\}\)\\)表示\\(\\mathcal\{S\}\\)\\(\\mathcal\{S\}\\)上的概率单纯形。对于两个概率分布\\(p,q\\)\\(p,q\\)，它们之间的全变差距离定义为\\(\\|p\-q\\|\_\{\\mathrm\{TV\}\}=\\frac\{1\}\{2\}\\|p\-q\\|\_1\\)\\(\\|p\-q\\|\_\{\\mathrm\{TV\}\}=\\frac\{1\}\{2\}\\|p\-q\\|\_1\\)。使用标准的大O记号：对于非负序列\\(a\_n,b\_n\\)\\(a\_n,b\_n\\)，\\(a\_n=O\(b\_n\)\\)\\(a\_n=O\(b\_n\)\\)若\\(a\_n\\leq Cb\_n\\)\\(a\_n\\leq Cb\_n\\)对某个通用常数\\(C\>0\\)\\(C\>0\\)成立；\\(a\_n=\\widetilde\{O\}\(b\_n\)\\)\\(a\_n=\\widetilde\{O\}\(b\_n\)\\)若\\(a\_n=O\(b\_n\\log^c\(1/\\delta\)\)\\)\\(a\_n=O\(b\_n\\log^c\(1/\\delta\)\)\\)对某个\\(c\>0\\)\\(c\>0\\)成立。我们写\\(x\\lesssim y\\)\\(x\\lesssim y\\)若\\(x\\leq Cy\\)\\(x\\leq Cy\\)，以及\\(x\\gtrsim y\\)\\(x\\gtrsim y\\)若\\(x\\geq Cy\\)\\(x\\geq Cy\\)，其中\\(C\>0\\)\\(C\>0\\)为通用常数。我们还写\\(x\\ll y\\)\\(x\\ll y\\)和\\(x\\gg y\\)\\(x\\gg y\\)表示尺度分离。特别地，我们使用\\(1\-O\(\\delta\)\\)\\(1\-O\(\\delta\)\\)表示某事件以至少\\(1\-C\\delta\\)\\(1\-C\\delta\\)的概率发生，其中\\(C\\)\\(C\\)为某常数。我们用\\(\\mathbf\{1\}\\)\\(\\mathbf\{1\}\\)表示全一向量，其维度由上下文确定。对于任意向量\\(\\bm\{x\},\\bm\{y\}\\in\\mathbb\{R\}^\{d\}\\)\\(\\bm\{x\},\\bm\{y\}\\in\\mathbb\{R\}^\{d\}\\)，我们使用\\(\\bm\{x\}\\leq\\bm\{y\}\\)\\(\\bm\{x\}\\leq\\bm\{y\}\\)表示对所有\\(i\\in\\\{1,\\ldots,d\\\}\\)\\(i\\in\\\{1,\\ldots,d\\\}\\)有\\(x\_i\\leq y\_i\\)\\(x\_\{i\}\\leq y\_\{i\}\\)。对于标量\\(x\\)\\(x\\)，令\\(\[x\]\_+\\coloneqq\\max\\\{x,0\\\}\\)\\(\[x\]\_\{\+\}\\coloneqq\\max\\\{x,0\\\}\\)；对于向量，\\(\[\\cdot\]\_+\\)\\(\[\\cdot\]\_\{\+\\}\\)逐坐标应用。令\\(\[N\]\\)\\(\[N\]\\)为\\(\\{1,\\ldots,N\\\}\\)\\(\\{1,\\ldots,N\\\}\\)。 ## 2 问题描述 本节建立鲁棒平均奖励MDP的模型以及决定样本复杂度的跨度参数。我们首先给出名义和鲁棒平均奖励MDP的基本定义。然后阐述结构假设，并解释高容差与低容差机制的划分。 ### 2.1 鲁棒平均奖励MDP ##### 标准平均奖励MDP。我们首先介绍标准平均奖励马尔可夫决策过程（AMDP），由\\(\\mathcal\{M\}^0=\(\\mathcal\{S\},\\mathcal\{A\},P^0,r\)\\)\\(\\mathcal\{M\}^\{0\}=\(\\mathcal\{S\},\\mathcal\{A\},P^\{0\},r\)\\)指定。这里，\\(\\mathcal\{S\}=\\\{1,\\ldots,S\\\}\\)\\(\\mathcal\{S\}=\\\{1,\\ldots,S\\\}\\)是状态空间，\\(\\mathcal\{A\}=\\\{1,\\ldots,A\\\}\\)\\(\\mathcal\{A\}=\\\{1,\\ldots,A\\\}\\)是动作空间，\\(P^0=\\\{P\_\{s,a\}^0\\\}\_\{(s,a)\\in\\mathcal\{S\}\\times\\mathcal\{A\}\}\\)\\(P^\{0\}=\\\{P\_\{s,a\}^\{0\}\\\}\_\{\(s,a\)\\in\\mathcal\{S\}\\times\\mathcal\{A\}\}\\)是转移核，其中\\(P\_\{s,a\}^0\\)\\(P\_\{s,a\}^\{0\}\\)是给定状态-动作对\\((s,a)\\)\\((s,a)\\)时的下一状态分布，而\\(r:\\mathcal\{S\}\\times\\mathcal\{A\}\\to\[0,1\]\\)\\(r:\\mathcal\{S\}\\times\\mathcal\{A\}\\to\[0,1\]\\)是奖励函数。一个平稳策略\\(\\pi:\\mathcal\{S\}\\to\\Delta\(\\mathcal\{A\}\)\\)\\(\\pi:\\mathcal\{S\}\\to\\Delta\(\\mathcal\{A\}\)\\)为给定状态\\(s\\in\\mathcal\{S\}\\)\\(s\\in\\mathcal\{S\}\\)指定动作选择规则，其中\\(\\pi\(s\)\\)\\(\\pi\(s\)\\)是动作空间上的概率分布。平均奖励衡量策略的长期稳态价值。对于转移核\\(P^0\\)\\(P^\{0\}\\)和策略\\(\\pi\\)\\(\\pi\\)，从初始状态\\(s\\)\\(s\\)开始的平均奖励为 \\[\\rho\_\{P^0\}^\{\\pi\}\(s\)\\coloneqq\\lim\_\{T\\rightarrow\\infty\}\\mathbb\{E\}\_\{P^0\}^\{\\pi\}\\left\[\\frac\{1\}\{T\}\\sum\_\{t=0\}^\{T\-1\}r\(s\_\{t\},a\_\{t\}\)\\mid s\_\{0\}=s\\right\],\\] 只要极限存在。期望值是在动作\\(a\_t\\sim\\pi\(s\_t\)\\)\\(a\_\{t\}\\sim\\pi\(s\_\{t\}\)\\)和下一状态\\(s\_\{t+1\}\\sim P^0\_\{s\_\{t\},a\_\{t\}\}\\)\\(s\_\{t\+1\}\\sim P^\{0\}\_\{s\_\{t\},a\_\{t\}\}\\)上取的。在核\\(P^0\\)\\(P^\{0\}\\)下，用 \\[\\rho\_\{P^0\}^\{\\star\}\(s\)\\coloneqq\\sup\_\{\\pi\}\\rho\_\{P^0\}^\{\\pi\}\(s\)\\] 表示从初始状态\\(s\\)\\(s\\)开始的最优平均奖励。 ##### 分布鲁棒AMDP。由于策略的性能可能对转移核的扰动敏感，分布鲁棒公式通过策略在名义核\\(P^0\\)\\(P^\{0\}\\)附近所有合理转移核下的最坏情况性能来评估策略。具体而言，一个分布鲁棒AMDP写为\\(\\mathcal\{M\}=\(\\mathcal\{S\},\\mathcal\{A\},P^0,\\mathcal\{U\},r\)\\)\\(\\mathcal\{M\}=\(\\mathcal\{S\},\\mathcal\{A\},P^\{0\},\\mathcal\{U\},r\)\\)，其中\\((\\mathcal\{S\},\\mathcal\{A\},P^0,r\)\\)\\((\\mathcal\{S\},\\mathcal\{A\},P^\{0\},r\)\\)是上述名义AMDP，而\\(\\mathcal\{U\}\\)\\(\\mathcal\{U\}\\)通过将转移核映射到一组转移核来描述允许的转移扰动。我们关注\\((s,a)\\)\\((s,a)\\)\-矩形全变差（TV）不确定集，这意味着每个状态-动作对的不确定性是解耦的。对于每个状态-动作对\\((s,a)\\)\\((s,a)\\)，给定一个局部半径\\(\\sigma\_\{s,a\}\\in\[0,\\sigma\]\\)\\(\\sigma\_\{s,a\}\\in\[0,\\sigma\]\\)。在\\(P^0\\)\\(P^\{0\}\\)附近的不确定集，记为\\(\\mathcal\{P\}\\coloneqq\\mathcal\{U\}\(P^0\)\\)\\(\\mathcal\{P\}\\coloneqq\\mathcal\{U\}\(P^\{0\}\)\\)，定义为 \\[\\mathcal\{U\}\(Q\)\\coloneqq\\prod\_\{(s,a\)\\in\\mathcal\{S\}\\times\\mathcal\{A\}\}\\mathcal\{U\}\_\{s,a\}\(Q\_\{s,a\}\)\),\\quad\\mathcal\{U\}\_\{s,a\}\(Q\_\{s,a\}\)=\\left\\\{P\_\{s,a\}\\in\\Delta\(\\mathcal\{S\}\):\\\|P\_\{s,a\}\-Q\_\{s,a\}\\\|\_\{\\mathrm\{TV\}\}\\leq\\sigma\_\{s,a\}\\right\\\},\\] 对于任何转移核\\(Q=\\\{Q\_\{s,a\}\\\}\\)\\(Q=\\\{Q\_\{s,a\}\\\}\\)。此外，令\\(\\mathcal\{P\}\_\{s,a\}\\coloneqq\\mathcal\{U\}\_\{s,a\}\(P\_\{s,a\}^0\)\\)\\(\\mathcal\{P\}\_\{s,a\}\\coloneqq\\mathcal\{U\}\_\{s,a\}\(P\_\{s,a\}^\{0\}\)\\)为状态-动作对\\((s,a)\\)\\((s,a)\\)处转移向量\\(P\_\{s,a\}^0\\)\\(P\_\{s,a\}^\{0\}\\)的不确定集。这里我们使用更广泛的不确定集类别，允许局部半径\\(\\sigma\_\{s,a\}\\)\\(\\sigma\_\{s,a\}\\)小于\\(\\sigma\\)\\(\\sigma\\)，而Shiet al. (2026 (https://arxiv.org/html/2608.06545#bib.bib3)) 假设对所有\\((s,a)\\)\\((s,a)\\)有\\(\\sigma\_\{s,a\}=\\sigma\\)\\(\\sigma\_\{s,a\}=\\sigma\\)。对于策略\\(\\pi\\)\\(\\pi\\)，鲁棒平均奖励是\\(\\mathcal\{P\}\\)\\(\\mathcal\{P\}\\)上的最坏情况平均奖励，而鲁棒最优平均奖励是这种最坏情况值中的最优值： \\[\\rho^\{\\pi,\\sigma\}\(s\)\\coloneqq\\inf\_\{P\\in\\mathcal\{P\}\}\\rho\_\{P\}^\{\\pi\}\(s\).\\]