📊 论文图表(共 3 张)

展开查看 3 张图

‹ ›

TL;DR

本文首次为有限期马尔可夫决策过程中精确执行的自然策略梯度算法提供了严格的有限时间收敛保证。在常数步长设定下，算法以 $\mathcal{O}(H^2/t)$ 的速率次线性收敛到最优策略；采用精心设计的递增步长调度时，可进一步加速至几何收敛速率 $\mathcal{O}((1-1/{\vartheta }_{\rho }{)}^t)$。该结果不仅填补了 NPG 理论分析在有限期场景下的空白，还通过推广至线性 MDP 表明收敛阶与状态-动作空间规模无关。

研究背景与动机

自然策略梯度（NPG）是强化学习领域最具影响力的理论基石之一，它为信赖域策略优化（TRPO）和近端策略优化（PPO）这两大主流算法提供了数学上的优雅解释。在实践中，这些方法已经在机器人控制、游戏博弈乃至大语言模型的人类反馈强化学习（RLHF）中展现出令人印象深刻的效果。然而，回顾已有的收敛性理论，几乎所有关于 NPG 的有限时间分析都隐含着一个默认假设：问题的决策过程是无限期且具有折扣因子的。

这一理论假设与真实应用场景之间存在显著鸿沟。现实世界中的许多序贯决策问题天然具有有限的时间跨度：机器人需要在一个任务周期内完成一系列动作，供应链管理中的多阶段决策有明确的终止节点，游戏中的对抗也往往在有限回合内分出胜负。这些场景用专业术语来说就是有限期马尔可夫决策过程，其转移核和奖励函数都依赖于当前所处的时域索引。这种时域依赖性带来了根本性的分析困难：最优策略不再是一个时间不变的决策规则，而是随时间变化的策略序列 $\pi =({\pi }_1,{\pi }_2,\dots ,{\pi }_H)$。

从理论角度看，有限期设定打破了无限期折扣 MDP 分析中的核心工具——由折扣因子诱导的压缩映射性质。当折扣因子 $\gamma <1$ 时，值函数的迭代更新天然具有收缩性，这为建立收敛保证提供了有力支撑。而在有限期设定下，这种结构性优势不复存在。更棘手的是，更新某一时刻 $h$ 的策略会改变后续时刻 $H$ 的状态分布，形成跨时域的复杂耦合效应。长期以来，研究社区缺乏对精确 NPG 在有限期 MDP 中收敛行为的理解，这一空白既阻碍了理论认知的完善，也使得实际算法设计缺乏可靠的方向指引。本文正是针对这一理论缺口展开系统研究。

方法

作者的核心思路是将自然策略梯度重新理解为一种策略空间上的镜像下降过程，从而借助优化理论的工具来分析其收敛行为。具体而言，NPG 的更新规则可以等价地表述为 KL-策略镜像下降（KL-PMD）：

这种重新表述揭示了 NPG 的本质：它是一个在策略分布空间中进行近端梯度下降的框架，目标函数由当前策略的动作值函数的期望驱动，正则化项由 KL 散度度量策略更新的幅度。

在常数步长的分析中，作者从三个技术支柱逐步搭建起完整的证明链条。首先是性能差引理，它建立了当前策略与最优策略之间值函数差异与策略梯度之间的关系。其次是 KL 单调性不等式，它保证了每一步策略更新都不会使目标函数下降。第三步是镜像下降的标准不等式，它将这些局部更新性质累积为全局收敛界。通过精心追踪 $H$ 个时域之间的依赖关系，最终证明经过 $t$ 次迭代后，值函数的次优性间隙被 $\mathcal{O}(H^2/t)$ 所控制。$H^2$ 因子的出现源于跨时域耦合效应的累积：当 $H$ 很大时，最早期策略的改进需要通过多层的状态分布传导才能影响最终性能。

为了突破次线性收敛的局限，作者引入了一个关键构造——多起点辅助目标函数。直觉告诉我们，有限期 MDP 的收敛瓶颈在于缺乏一个统一的"全局度量"来引导所有时域的策略改进。如果我们在时域上均匀随机化目标，便能为每个时刻提供一个与具体策略无关的下界分布。形式化地，定义：

其中 $\rho$ 是初始状态分布。通过这一构造，可以定义分布失配系数 ${\vartheta }_{\rho }$ 来刻画初始分布与最优状态下分布之间的偏差程度。当步长满足增长条件 ${\eta }_{t+1}\ge \frac{{\vartheta }_{\rho }}{{\vartheta }_{\rho }-1}{\eta }_t$ 时，算法展现出几何收敛的锐利特性。特别令人惊喜的是，引理证明 ${\vartheta }_{\rho }\ge H$ 总是成立，这意味着一个完全问题无关的步长调度 ${\eta }_t={\eta }_0{\left(\frac{H}{H-1}\right)}^t$ 天然满足增长条件，无需知道 ${\vartheta }_{\rho }$ 的精确值。

在线性 MDP 的推广中，作者采用精确总体投影预言机来参数化策略。关键观察是：当投影分布具有全支撑时，零投影损失退化为逐点恒等式，此时参数空间的梯度更新在策略空间精确地诱导出与表格情形相同的更新。这表明收敛速率的本质只取决于 MDP 的结构特性，而与状态-动作空间的规模无关。

实验与结果

作者在小型合成 MDP 上设计了三组实验，旨在验证理论预测的收敛行为而非追求与最新方法的性能对比。

第一组实验针对次线性收敛进行验证。论文设定 $|\mathcal{S}|=15$、$|\mathcal{A}|=4$、$H=7$ 的随机表格 MDP，图 1a 固定时域 $h=1$ 运行 $T=500$ 次迭代，对比经验性能差距与理论界 $2H^2/t$；图 1b 则固定迭代次数 $T=100$，扫描不同起始时域 $h$ 并与预测界 $2(H-h+1{)}^2/T$ 对照。实验曲线与理论界的吻合程度验证了分析的正确性。

第二组实验聚焦于几何收敛的验证。作者精心构造了一个双重随机链 MDP：转移核以 $0.7$ 的概率保持当前状态、以 $0.3$ 的概率沿环形结构前移。这种结构使得均匀分布对所有策略保持不变，从而 ${\vartheta }_{\rho }=H$ 达到最坏情形下界。图 2a 展示了 $h=1$ 处确实呈现 $(1-1/H{)}^t$ 的指数衰减，图 2b 则通过 tail MDP 实验验证了各时域的几何收敛行为。

第三组实验在随机 MDP 上重复几何收敛验证，通过从对称 Dirichlet 分布采样转移核、i.i.d. 均匀奖励来排除结构化实例可能带来的巧合。结果表明即使在随机设定下，经验收缩因子也与理论预测一致，进一步巩固了分析的普适性。

讨论与可借鉴点

这项工作最核心的理论贡献在于填补了 NPG 在有限期 MDP 场景下有限时间分析的空白。它向研究社区传递了一个明确信号：即使在缺乏折扣压缩支撑的困难设定下，通过巧妙的分析技术仍然可以获得有意义的时间收敛保证。多起点目标函数的构造尤其值得关注——它展示了一种处理跨时域耦合的标准范式：通过在时间维度上引入均匀化，可以将问题相关的分布偏差转化为可分析的常数。

当然，这项分析也存在若干值得关注的局限性。作者坦诚地承认，$H^2$ 因子是否反映问题本质还是仅为证明技术的产物，目前尚不清楚——这给出了一个明确的下界最优性问题。另一个局限在于，几何收敛的结果仅直接控制 $h=1$ 时刻的收敛，其他时域的收敛性质需要通过额外的 tail MDP 变换间接获得。此外，分析完全建立在动力学已知的前提之上，样本基设定下值函数估计误差如何影响收敛速率仍是未解决的问题。

对于未来的研究而言，这篇论文提供了一个坚实的理论基线。理解有限期设定下 $H^2$ 因子的最优性、探索样本基 NPG 的收敛行为、以及将分析推广至函数近似更强的设定，都是值得关注的方向。值得再次强调的是，当动力学已知时反向归纳可以一步求得最优策略，因此这篇论文的理论贡献不在于提出更快算法，而在于为平滑策略更新范式和样本基扩展提供可靠的理论保障。

摘要

自然策略梯度（NPG）是一种成熟的强化学习算法，是信赖域策略优化（TRPO）和近端策略优化（PPO）等广泛使用方法的理论基础，这些方法均在实证中展现出强大的性能。在本文中，我们研究在已知动力学且转移核依赖于步数的有限期马尔可夫决策过程中的精确自然策略梯度算法。我们首次为该算法在此设定下提供了有限时间收敛性保证，并分别考虑了常数步长与递增步长两种情形。在常数步长 ${\eta }_t=\eta$ 下，我们证明自然策略梯度在 $t$ 次迭代后以 $\mathcal{O}(H^2/t)$ 的速率次线性收敛，其中 $H$ 为步数长度。我们还将该常数步长分析推广至线性 MDP，在全支撑投影分布下使用精确总体投影预言机，恢复出与表格设定相同的次线性收敛速率。此外，采用递增步长时，我们证明该算法对某个问题相关常数 ${\vartheta }_{\rho }>1$ 实现了 $\mathcal{O}\left({\left(1-\frac{1}{{\vartheta }_{\rho }}\right)}^t\right)$ 的线性收敛速率；而仅依赖于步数的鲁棒调度 ${\eta }_t={\eta }_0(H/(H-1){)}^t$（其中 ${\eta }_0>0$ 且 $H\ge 2$）也达到了相同的几何收敛速率。

Abstract

Natural Policy Gradient (NPG) is a well-established Reinforcement Learning algorithm that underlies widely used methods such as Trust Region Policy Optimization and Proximal Policy Optimization, both of which have demonstrated strong empirical success. In this paper, we study exact NPG in finite-horizon Markov Decision Processes with known dynamics and horizon-dependent transition kernels. We provide the first finite-time convergence guarantees for this algorithm in this setting, for which we consider both constant and increasing step size regimes. With a constant step size ${\eta }_t=\eta$, we prove that NPG converges sublinearly with a rate of $\mathcal{O}(H^2/t)$ after $t$ iterations, where $H$ is the horizon length. We also extend this constant step size analysis to linear MDPs in an exact population-projection oracle under a full support projection distribution, recovering the same sublinear rate as in the tabular setting. Furthermore, with increasing step sizes, we prove that this algorithm achieves a linear convergence rate of $\mathcal{O}\left({\left(1-\frac{1}{{\vartheta }_{\rho }}\right)}^t\right)$ for a problem-dependent constant ${\vartheta }_{\rho }>1$, and the horizon-only robust schedule of the form ${\eta }_t={\eta }_0(H/(H-1){)}^t$ where ${\eta }_0>0$ and $H\ge 2$, attains this same geometric rate.

论文详细总结（自动生成）

论文总结：有限期马尔可夫决策过程中自然策略梯度的有限时间分析

1. 核心问题与整体含义

自然策略梯度（NPG）是强化学习中信赖域策略优化（TRPO）和近端策略优化（PPO）的理论基础。然而，已有 NPG 收敛分析主要针对无限期折扣 MDP 设定，无法直接覆盖实践中大量存在的有限期 MDP 场景。有限期 MDP 带来两个本质性结构困难：

• 非平稳最优策略：最优策略通常为时域相关的决策规则序列 $\pi =({\pi }_1,\dots ,{\pi }_H)$，更新某个时域的决策会改变后续时域的状态分布，形成跨时域耦合。
• 缺乏折扣诱导的压缩：无限期折扣 MDP 分析中常用的严格压缩性质在有限期设定下不再适用，转移核和值函数都依赖于时域索引 $h$。

尽管有限期 MDP 在序列规划、机器人操作以及大语言模型 RLHF 等场景中具有重要实践意义，但精确 NPG 在该设定下的有限时间收敛性长期缺乏理论保证。本文正是为填补这一空白。

2. 方法论

2.1 设定与算法核心

有限期 MDP 表示为 $(\mathcal{S},\mathcal{A},H,P,R)$，其中转移核 $P=\{P^h:h=1,\dots ,H\}$ 与奖励 $R=\{R^h\}$ 均依赖于时域 $h$，$\pi =({\pi }_1,\dots ,{\pi }_H)$ 为非平稳策略。值函数满足 $0\le V^{\pi ,h}(s)\le H-h+1$。

NPG 更新采用乘法形式：

其等价于 KL-策略镜像下降（KL-PMD）：

2.2 常数步长：次线性收敛（定理 1）

在表格 MDP 中，从均匀初始化 ${\pi }^0(\cdot \mid s)=\mathrm{Unif}(\mathcal{A})$ 出发，NPG 在任意时域 $h\in [H]$、状态 $s\in \mathcal{S}$ 满足：

当 $\eta \ge \log |\mathcal{A}|/(H-h+1)$ 时，主项简化为 $\mathcal{O}((H-h+1{)}^2/T)$；$H^2$ 因子的来源是引理 15 中 ${\sum }_{i=H-j}^H(H-i+1)=(j+1)(j+2)/2$ 的求和。

2.3 线性 MDP 推广（命题 1）

在 Jin 等人 [2020] 的线性 MDP 假设下，采用全支撑投影分布 $v(s,a)>0$ 与精确总体投影预言机

由于 $v$ 全支撑，零投影损失退化为逐点恒等式 $⟨w_{{\pi }_t,h},\varphi (s,a)⟩=Q^{{\pi }_t,h}(s,a)$。由此 Q-NPG 参数更新

在策略空间精确诱导出表格 NPG 更新，从而继承相同的 $\mathcal{O}(H^2/t)$ 收敛速率。

2.4 递增步长：几何收敛（定理 2 与推论 1）

为获得几何收敛，引入多起点辅助目标：

关键观察：均匀分布 $H_0\sim \mathrm{Unif}\{1,\dots ,H\}$ 为每个时域 $i$ 提供策略无关的下界

定义多起点分布失配系数

并要求步长满足增长条件

则对所有 $t\ge 0$：

引理 9 证明 ${\vartheta }_{\rho }\ge H$，因此仅依赖时域的鲁棒步长调度

无需已知 ${\vartheta }_{\rho }$ 即可满足增长条件。最优情形 ${\vartheta }_{\rho }=H$ 时达到收缩因子 $1-1/H$。引理 9 论证（详见 Appendix B.2）：对每个 $i$ 取期望得 ${\mathbb{E}}_{\rho }[{\bar{d}}_{i,\rho }^{{\pi }^{\star }}(S)/\rho (S)]=i/H$，因此最大值至少为 $i/H$，取 $i=H$ 得 ${\vartheta }_{\rho }\ge H$。

3. 实验设计

实验在小型合成 MDP 上进行，用以验证理论预测的收敛行为，而非作为大规模基准比较：

• 次线性收敛实验（图 1）：随机生成的表格 MDP，$|\mathcal{S}|=15$，$|\mathcal{A}|=4$，$H=7$。图 1a 固定 $h=1$，运行 $T=500$ 次迭代，对比经验误差与理论界 $2H^2/t$；图 1b 固定 $T=100$，绘制各时域的经验误差与上界 $2(H-h+1{)}^2/T$。
• 几何收敛实验（图 2）：构造结构化实例 $|\mathcal{S}|=15$，$|\mathcal{A}|=5$，$H=7$，转移核 $P^h(s^{\prime }|s,a)=0.7\cdot 1\{s^{\prime }=s\}+0.3\cdot 1\{s^{\prime }=s+1(\mathrm{mod}|\mathcal{S}|)\}$（双重随机），使均匀分布在所有策略下不变，从而 ${\vartheta }_{\rho }=H$。使用推论 1 的鲁棒调度，图 2a 验证 $h=1$ 的 $(1-1/H{)}^t$ 收缩；图 2b 固定 $T=20$ 验证各时域 tail MDP 上的几何收敛。
• 随机 MDP 上的几何收敛实验（图 3，附录 B.1）：从对称 Dirichlet（单位浓度）采样转移核、i.i.d. 均匀奖励，随机种子 42；通过反向归纳计算 ${\pi }^{\star }$ 并实测 ${\vartheta }_{\rho }>H$，验证理论界并非仅由结构化实例保证。

4. 资源与算力

论文未明确报告任何计算资源或算力消耗（无 GPU 型号、数量、训练时长等信息）。鉴于实验仅涉及小规模表格 MDP（$|\mathcal{S}|\le 15$，$|\mathcal{A}|\le 5$，$H\le 7$，迭代次数 $T\le 500$），计算开销极低，单 CPU 即可在秒级时间内完成全部数值实验。

5. 实验数量与充分性

共报告 3 组主实验（次线性 1 组 + 几何收敛结构化 1 组 + 几何收敛随机 1 组），外加若干子图（不同固定迭代数 / 跨时域扫描）。

• 充分性评估：实验目的是验证理论界的预测行为（收敛阶、时域依赖、${\vartheta }_{\rho }$ 的界），而非比较不同 RL 算法的实证性能。每组实验均同时绘制经验曲线与理论曲线，并附随机 MDP 实例以排除结构巧合；tail MDP 实验进一步独立验证了 ${\vartheta }_{\rho }=H-h+1$ 的预测。
• 局限：缺乏与 PPO/TRPO 等基于 NPG 的现代方法的对比，也未在更大规模 MDP（如 Atari 控制任务、RLHF）上验证；样本-基（inexact）情形尚未涉及。

6. 主要结论与发现

• 首次为有限期 MDP 中的精确 NPG 提供了有限时间收敛保证。
• 常数步长：表格与线性 MDP 下均获 $\mathcal{O}(H^2/t)$ 次线性收敛速率。
• 递增步长：通过引入多起点目标 $J(\pi )$ 与分布失配系数 ${\vartheta }_{\rho }$，证明几何收敛 $\mathcal{O}((1-1/{\vartheta }_{\rho }{)}^t)$。
• 鲁棒性：仅依赖 $H$ 的步长调度 ${\eta }_t={\eta }_0(H/(H-1){)}^t$ 不需要已知 ${\vartheta }_{\rho }$ 即可满足增长条件，${\vartheta }_{\rho }\ge H$ 的下界使得调度对所有满足支撑条件的 MDP 均有效。
• 均匀分布 $H_0\sim \mathrm{Unif}$ 是最坏情形鲁棒意义下的最优选择（最大化 $m_{\min }$）。

7. 优点

• 理论新颖性：填补了 NPG 在有限期 MDP 上有限时间分析的空白，弥补了与无限期折扣 MDP 理论之间的差距。
• 方法论严密性：从性能差引理、KL 单调性、镜像下降三步不等式出发，构造完整技术链条；引理 4 通过均匀多起点提供了关键策略无关下界，巧妙绕开了有限期场景无折扣压缩的核心困难。
• 推广到线性 MDP：通过精确投影预言机将表格结果自然推广，揭示表示维度仅影响存储而非收敛阶。
• 实用步长调度：$H/(H-1)$ 增长因子完全由已知量 $H$ 决定，无须问题调参，具有良好实用性。
• 均匀加权的最优性论证：对 $H_0$ 的非均匀加权进行权衡分析，明确了 $1/m_{\min }$ 与 $1/m_1$ 之间的此消彼长关系。
• 实验验证清晰：数值结果与理论界的对比在子图层面一致，且在随机 MDP 上重复实验，避免结构化实例的特殊性。

8. 不足与局限

• $H^2$ 因子的最优性未知：作者明确指出尚不知 $H^2$ 对常数步长 NPG 是否必要，或仅为证明技术的人为产物；有限期情形下 PMD 的匹配上下界仍是开放问题。
• 多起点构造的代价：几何收敛结果仅控制 $h=1$ 的次优性间隙，其他时域 $h>1$ 需要通过 tail MDP 间接获得；引理 3 引入了 $H$ 倍损失。
• ${\vartheta }_{\rho }$ 的精确刻画：仅给出下界 ${\vartheta }_{\rho }\ge H$ 与上界 ${\vartheta }_{\rho }\le H/{\min }_s\rho (s)$（或 $\le H|\mathcal{S}|$ 当取 $\rho =\mathrm{Unif}$），问题相关的更紧界尚不清楚。
• 精确已知动力学假设：分析与 oracle 推广均建立在转移核与奖励完全已知的假设之上；样本-基（inexact）情形留作未来工作，未处理有限样本下动作值估计误差对收敛的影响。
• 实验规模有限：仅在 $|\mathcal{S}|\le 15$ 的小型合成 MDP 上验证，缺乏在真实大规模任务或与 PPO/TRPO 等实际方法的对比。
• 与动态规划的对比：作者明确承认当动力学已知时反向归纳可一步得到最优策略，NPG/PMD 在计算上无优势；其分析价值在于为平滑策略更新与样本基扩展提供理论基线，而非提供更快的算法。
• $H=1$ 的退化情形：当 $H=1$ 时 ${\vartheta }_{\rho }=1$，增长因子 ${\vartheta }_{\rho }/({\vartheta }_{\rho }-1)$ 未定义，递增步长方案不适用。

（完）