Strongly Polynomial Time Complexity of Policy Iteration for $L_\infty$ Robust MDPs

技术摘要：针对 $L_\infty$ 鲁棒 MDP 的策略迭代算法具有强多项式时间复杂度

问题陈述
本文解决了一个关于序列决策领域中一个基础性的开放问题：在具有固定折扣因子和 $L_\infty$ 不确定性集的鲁棒马尔可夫决策过程（RMDPs）中，是否存在强多项式时间算法。虽然经典的 MDP 存在用于精确值计算的强多项式算法（Ye, 2011），且通过线性规划（LP）可以实现 RMDP 的多项式时间算法，但关于 RMDP 是否能拥有“强”多项式算法（即算术操作的数量与输入系数的位长无关）的问题仍未得到解决。具体而言，以往试图将 $(s, a)$-矩形 RMDP 归约为回合制随机博弈（turn-based stochastic games）的尝试之所以失败，是因为表示 $L_\infty$ 不确定性多胞体需要指数级的动作数量，导致无法实现多项式时间归约。

模型与定义
作者专注于具有 $L_\infty$ 不确定性集 的 $(s, a)$-矩形 RMDP。

• $(s, a)$-矩形性： 环境为每个状态-动作对独立地选择转移概率，从而保持了动态规划的结构。
• $L_\infty$ 不确定性： 对于每个状态-动作对 $(s, a)$，真实的转移向量位于以标称估计 $\hat{P}_{s,a}$ 为中心、半径为 $\delta_{s,a}$ 的 $L_\infty$ 球内。
• 目标： 智能体寻求一个策略 $\sigma$，以最小化在对抗性环境策略 $\tau$ 下的最坏情况期望成本。
• 强多项式时间： 如果一个算法的算术操作次数受限于变量和约束数量的多项式，且计算过程中的数值大小与输入系数的位长无关，则称该算法为强多项式算法。

方法论
本文分析了 鲁棒策略迭代（PI） 算法，该算法在策略评估（Policy Evaluation）和策略改进（Policy Improvement）之间交替进行。

1. 鲁棒马尔可夫链（RMCs）： 作者首先分析了更简单的情形，即智能体在每个状态下只有一个动作的情况（RMC-PI）。

   • 策略改进： 为了避免依赖于位精度的线性规划（LP），作者利用 同伦算法（Homotopy Algorithm）（Behzadian et al., 2021）来计算最优环境响应。该算法运行时间为 $O(n \log n)$，并产生具有特定结构属性的策略：转移概率通过将质量从“捐赠者”状态移动到“接收者”状态来进行调整，直到触及边界（0、1 或不确定性半径）。
   • 势函数（Potential Function）： 引入了一个新的势函数 $f_\tau(s, s', s'')$ 来追踪同伦算法允许的概率质量转移。该函数衡量了通过将质量从一个较低的最优值状态转移到较高的最优值状态所带来的潜在改进。
   • 组合界限： 作者证明了当前策略的转移概率与最优转移概率之间的“差异”（discrepancy）呈几何级数下降。至关重要的是，他们建立了一个关于实数有符号子集和中不同最高有效位（MSB）数量的组合引理（引理 8）。该引理源自一个更通用的定理（定理 20/21），它将可能的 MSB 数量限制在 $O(|X| \log |X|)$。
   • 收敛论证： 通过结合价值误差的几何收缩（引理 2）与差异的有限个 MSB（引理 8），作者表明算法无法无限进行任意小的更新。差异的 MSB 必须在多项式次内发生变化。

2. 鲁棒 MDP（RMDPs）： 将分析扩展到一般的 RMDP 情况（RMDP-PI）。

   • 算法通过为当前的智能体策略求解 RMC 子问题来迭代寻找最坏情况的环境响应，然后更新智能体策略以最小化产生的成本。
   • 定义了类似的针对动作的势函数，用于追踪偏离最优智能体动作的成本。
   • 同样的逻辑适用：在价值误差收缩迫使变化之前，具有最大势能的动作无法持续超过对数次迭代。

核心贡献与结果

• 强多项式 RMC-PI： 作者证明，对于具有 $n$ 个状态和常数折扣因子 $\gamma$ 的 RMC，鲁棒策略迭代的终止时间为 $O(n^4 \log n \cdot \frac{\log((1-\gamma)/n^2)}{\log \gamma})$ 次迭代。由于每次迭代都涉及多项式时间的操作（矩阵求逆和同伦步骤），因此总运行时间是强多项式的。
• 强多项式 RMDP-PI： 该结果被推广到具有 $n$ 个状态和 $m$ 个动作的 RMDP。算法在 $O(n \cdot m \cdot \frac{\log(1-\gamma)}{\log \gamma})$ 次迭代内终止，确立了 RMDP-PI 也是强多项式的。
• 组合引理： 本文引入了引理 8，这是一个全新的组合学结果，用于界定有符号子集和中不同 MSB 的数量，它是复杂度证明的核心。作者指出，该定理的一个更强版本是由 AI 研究代理（Aletheia）独立推导出的，这凸显了 AI 对数学领域的贡献。

意义与主张
本文声称解决了鲁棒优化理论中的一个重大开放问题。通过证明鲁棒策略迭代算法对于 $(s, a)$-矩形 $L_\infty$ RMDPs 具有强多项式时间复杂度，作者将 Ye (2011) 关于经典 MDP 的开创性结果推广到了鲁棒设定。这一结果的意义在于：

1. 它提供了计算 RMDP 精确值（而非近似值）的理论保证，且不依赖于输入参数的位长。
2. 它克服了以往因动作数量指数级爆炸而失败的归约技术的局限性。
3. 它确立了尽管存在无限的不确定性集，但鲁棒贝尔曼算子（robust Bellman operator）仍然可以利用同伦算法的组合特性进行高效导航。

作者总结道，虽然理论基础现已建立，但未来的工作可以探索基于数据的观测不确定性集，以及这些基于势能的论证是否可以引导出改进的实际变体或停止准则。他们还指出，关于标准 MDP 策略迭代变体的多项式界限问题仍然是一个开放课题。