第 9-1 章。稳健的 MDP
推荐阅读：【控制理论】【随机控制理论】(https://jb243.github.io/pages/895)
1. 总体概述
2. 有限范围鲁棒MDP
3. 无限视野鲁棒MDP
4. 示例
b. Arnab Nilim 和 Laurent El Ghaoui (2003)， (2004)
1.总体概述
⑴ 简介
① 目标：在模型模糊性下选择稳健的策略（即转移概率 P 模糊）
○ 不确定性：概率分布已知，但根据该概率存在随机性。
○ 模糊性：概率分布本身未知。换句话说，尚不清楚哪种分布是正确的。
② 问题定义
○ 标准MDP
○ 鲁棒 MDP：对于每个策略 π，问题是找到最坏情况的转移概率 P。
○ 问题 1. DP 最优策略对转移概率的微小变化非常敏感。
○ 下雨概率 0.3 → 最适合带伞。
○ 下雨概率 0.2 → 最好不带伞。
○ 仅相差0.1，但最优策略发生变化。
○ 问题 2. 每个 (s, a) 都添加了一个内部最小化 infp∈𝒫(s,a) 𝔼p[·]，使其计算量比标准 MDP 更重。
○ 问题 3. 线性规划的不可能性：根据 𝒫 的选择，它可以变成非凸的。
○ 固定转移矩阵 P：半空间的交集 → 凸。
○ infP 具有 ≥ 约束：凹屋顶的铭文 → 通常是非凸的。
○ 总结： 在本文中，“非凸问题”是指当整体模糊集 P 为非矩形时，自然最坏情况的选择变得暂时耦合，并且内部下确界优化失去了其良好的凸结构。矩形假设通过将 P 分解为每个阶段和每个状态-动作对的凸集来解决这个问题，以便鲁棒贝尔曼方程中的内下确界得到明确定义，并且仍然是一个凸优化问题。
③解决方案
○ 矩形假设：意味着每个时间步的转移概率的“选择”是独立于其他的。
○ 介绍目的：使DP分解（贝尔曼递归）成为可能。
○ 比简单的统计独立性更强的假设。通常适用于固定政策。
○ ℳ(ℬ)：离散集 ℬ 上的概率度量集。»> ○ 𝒯dt：符合历史相关决策规则 dt 的条件分布集。为了描述条件分布，必须指定动作 a 和下一状态 st+1 的联合分布 ph(a,s)。
○ ×：笛卡尔积，因此 𝒯π 的每个元素都是每阶段分布的元组，例如 (p0, p1, …, pN-1)。
○ π 没有明确出现在 𝒯π 中，因为它是通过 dt 定义的，但当 π 改变时，dt 也会改变，因此𝒯π 也会改变。
○ 结果： 计算变得容易处理（减轻维数灾难），并且如果 𝒫(s, a) 是凸的，则内部问题也是凸的。
○ 限制： 如果过渡动力学快速发展，允许大自然在每次访问时选择不同的最坏情况过渡分布（如矩形假设）可能是相当现实的。但是，如果转换模型仅缓慢变化，那么假设每次遇到相同的 (s,a) 对时，自然都会敌对地切换到全新的分布，特别是在这种频繁重访的无限视野环境中，就变得不现实了。
○ 对抗性设置
○ 鲁棒 MDP 是定义 π 的决策者与寻找每个 π 的下确界的对手之间的博弈。
○ 问题1. 由于博弈论和优化在概念上不同，鲁棒MDP更接近博弈论还是优化论？
| 优化 | 游戏 |
|---|---|
| f(x) | minx∈X minxi ∈ Xi fi(xi, x-i), i ∈ [N] |
| （强）凸性 | （强）单调性 |
| (cvx) 全局最小化 | (cvx) NE: fi(xi, x-i) ≤ fi(xi, x-i*) 对于 i ∈ [N] |
| (ncvx) B-/Clarke 平稳性 | (ncvx) 准/克拉克 NE |
表1. 优化理论和博弈论之间的区别
○ 问题2. 单代理系统不影响吗？
○ 答案： 矩形假设用单智能体优化理论简化了问题。
○ 完美观察 MDP：观察状态 st 并选择 at。
○ 时间不变：奖励 rt(st, at, st+1) 已知，并且在无限范围情况下，时间不变。
⑵ 背景理论
① DP(动态规划)
② ϵ-最优策略
③【巴纳赫不动点定理】(https://jb243.github.io/pages/1827)
④【博弈论】(https://jb243.github.io/pages/1914)
⑤【信息论】(https://jb243.github.io/pages/2145)
2.有限范围鲁棒 MDP
⑴ 概述：对于计算来说，状态/动作空间是有限的。
⑵ 策略π固定后的价值函数。
① 由于 st+1 是不明确的，我们允许时间 t 的奖励也取决于 st+1：rt(st, at, st+1) 而不是 rt(st, at)。
⑶ 贝尔曼方程（DP）
①简单证明
> ② 严格证明：使用 ϵ 最优策略和等价方法（同时显示 LHS ≥ RHS 和 LHS ≤ RHS）。
3。无限视野鲁棒 MDP
⑴ 概述：在折扣因子 λ < 1 和矩形不确定性下，鲁棒 Bellman 算子也是收缩的 → 值/策略迭代收敛。
⑵ 贝尔曼方程（DP）
⑶巴拿赫不动点定理
① 推论：inf 和sup 不会改变Banach 不动点定理的结论（关键结果）。请注意，(b) 是一个 NP 完全问题。
② 值迭代算法
○ 收缩性 → 当前残差的误差界限。
○ 一个更新步骤的错误。
○ 因此，要保证ㅣㅣṼ - V*ㅣㅣ ≤ ϵ / 2。
○ 论文的算法添加了一个额外的 1/2 乘数，并在满足该条件时停止。
○ 这个更严格的限制确保即使在更新 V ← Ṽ 后，误差仍然足够小（三角不等式的额外余量），因此在下一步选择贪心策略时，也满足性能损失界限（通常为 (2λ / (1 - λ)) ㅣㅣV - V*ㅣㅣ）——一个保守的（安全余量）设置。
③ 策略迭代算法
⑷ 决策者与对手之间的不对称
① 如果仅考虑平稳策略，在矩形、贴现无限视野和凸/紧 P(s, a) 下，即使动态对手可以每次访问改变选择，对平稳策略的最优响应也是“平稳”的（每个 (s,a) 具有相同的 p），产生相同的值。
② 动态对手看起来更强，但在固定政策下，实际最坏情况的反应是静态的，具有同等价值。
③ 然而，当对手静止时，决策者的静止政策可能不是最优的。更好的选择可能是随时间/历史调整权重的非固定/动态（通用）策略（Cover，1991）。
4。示例
⑴ 概述
① 由于 infp 引起的非凸性，整个 V 问题很难通过线性规划求解。> ② 该方法通过DP（值/策略迭代）处理外部结构，并快速凸地求解内部最小化。
③ 下面的例子表明，鲁棒MDP比纯MDP更重，但时间复杂度并没有显着增加
④ 总结
| 不确定性集 | 普通 DP（每个状态-动作） | 鲁棒DP（每个状态-动作） |
|---|---|---|
| KL 置信度 | 𝒪(ㅣSㅣ) | 𝒪(ㅣSㅣ)（常数倍的增加） |
| L2（χ2-型）组 | 𝒪(ㅣSㅣ) | 𝒪(ㅣSㅣlogㅣSㅣ) |
| L1 套 | 𝒪(ㅣSㅣ) | 𝒪(ㅣSㅣlogㅣSㅣ) |
⑵ 应用1. KL信心
①概述：内部问题简化为一维凸搜索（指数倾斜形式解）。
② 数据 → KL 散度： 根据 (s, a) 中观测到的频率，构建 MLE p̂sa，并通过代数统计（卡方近似），将置信区域（置信水平 ω）定义为 𝒫(s, a) = {p: D(p ㅣㅣ p̂sa) ≤ tω}。
③ 鲁棒期望+一维凸问题的闭式解： 求解 minpε𝒫 𝔼p[v] 的拉格朗日函数，得到 f(γ) = γt + γlog(𝔼q[exp(-v / γ)])，一个一维凸函数，具有最优分布 p(s) ∝ q(s) exp((μ - v(s)) / γ)，即指数倾斜。所以一旦找到γ，就可以直接得到p。
④ 计算复杂度保证： f’(γ) 是单调/凸 → 二分法有效地找到 ϵ 近似值（每个 f’(γ) 评估是 𝒪(ㅣSㅣ)）。
⑤ 结论： 使用 KL 置信集对鲁棒 MDP 中的转移不确定性进行建模，产生封闭形式的快速一维凸优化（指数倾斜），使计算高度实用。
⑶ 应用2. L2近似（χ2型）集
① 概述：一旦排序，阈值处理就可以实现快速计算→使得计算量大的鲁棒MDP实际上可以解决。
② 优化 infp∈𝒫 𝔼p[v] 可以在 𝒪(ㅣ𝒮ㅣ log(ㅣ𝒮ㅣ)) 时间内解决。
⑷ 应用3. L1近似集
① D(p ㅣㅣ q) ≥ (1 / 2 ln 2) ㅣㅣp - qㅣㅣ12 → 𝒫 = {p: ㅣㅣp - qㅣㅣ1 ≤ δ}，使用 δ = √(2t ln2)。
② L1 / L∞ 类型的集合方便建模，但作为统计置信区域较弱 → 在实践中，更推荐基于 L2 的集合。
输入：2025.10.27 20:40