📄 论文页面预览(共 6 页)

论文无独立配图,展开查看 6 页整页预览

‹ ›

TL;DR

这篇论文解决了平均奖励约束马尔可夫决策过程中神经评论家无法达到阶最优收敛的难题。核心贡献是提出分层多水平蒙特卡洛（HiMLMC）神经评论家，通过在外层随机化评论家优化迭代、内层随机化轨迹长度的双重去偏，以对数级样本成本达到长时间优化才能实现的偏差。基于此设计的原始-对偶自然执行器-评论家算法，首次在无需已知混合时间的条件下实现了 $\tilde{O}(T^{-1/2})$ 的最优性差距和约束违反，与该问题的 minimax 下界相匹配。

研究背景与动机

约束马尔可夫决策过程（CMDP）为安全关键应用中的强化学习提供了标准建模框架。在这类问题中，智能体不仅需要最大化长期平均奖励，还必须同时满足长期约束——这使得问题比标准马尔可夫决策过程更加复杂。无论是交通信号控制、通信网络资源分配、机器人安全操作还是医疗决策，都面临这类需要平衡性能与安全约束的实际挑战。

平均奖励准则相较于折扣准则更直接刻画稳态性能，特别适用于持续运行的决策任务。对于基于线性评论家的原始-对偶执行器-评论家方法，学术界已建立了较为完善的理论体系，能够达到 $\tilde{O}(T^{-1/2})$ 的收敛率，这与平均奖励强化学习的 minimax 样本复杂度下界是匹配的。然而，当评论家由神经网络参数化时，问题变得棘手得多。

扩展到神经评论家的核心困难在于一种根本性的偏差-成本权衡。在神经切线核（NTK）框架下分析会发现：为了维持线性近似的有效性，评论家更新需要在参数空间中进行投影，而这种投影导致评论家偏差的平方衰减速率与均方误差相同。要进一步降低偏差，需要显著增加评论家优化的迭代次数。但在原始-对偶嵌套架构下，外层策略迭代可支配的计算资源有限，这使得评论家的平方偏差停留在常数级别，无法达到阶最优收敛所要求的 $\tilde{O}(T^{-1})$ 量级。正是这一瓶颈导致此前神经执行器-评论家算法在平均奖励 CMDP 中只能达到 $\tilde{O}(T^{-1/4})$ 的收敛率，与理论下界存在显著差距。

方法

论文的核心创新是提出分层多水平蒙特卡洛（HiMLMC）神经评论家，通过在两个层面同时执行去偏来打破上述偏差-成本权衡。这里的关键洞察是：如果能够以较小样本成本模拟"长时间评论家优化"的效果，就能在不增加实际优化开销的前提下消除优化偏差。

外层多水平蒙特卡洛针对评论家优化迭代进行随机化。具体而言，采样随机变量 $H_k\sim \text{Geom}(1/2)$，然后基于此定义复合采样长度 $h_k=1+1\{2^{H_k}\le H_{\max }\}(2^{H_k}-1)$。由此构造的评论家估计量不仅使用了长度为 1 的基础样本，还以 $2^{H_k}$ 的系数叠加了长度为 $h_k$ 和 $h_k/2$ 的校正项。这一设计的精妙之处在于：通过精心选择的分布与系数组合，估计量的期望恰好等于在长度 $h_k$ 上独立采样 $2^{H_k}$ 次再做平均的结果，但样本成本却仅增长对数级别。用更直观的话说，我们以常数级的额外采样，换取了指数级延长的优化轨迹所带来的偏差消除效果。

内层多水平蒙特卡洛则针对轨迹采样长度进行去偏。与外层类似，通过几何分布随机化内层采样深度 ${\ell }_{k,h}$，在内层梯度估计 ${\hat{v}}_{k,h}^{u,\text{MLMC}}$ 上构造多层校正。最终的评论家参数更新采用带投影的随机梯度下降，投影保证了参数始终位于以初始化为中心的 NTK 球内：

其中学习率 ${\gamma }_{\xi ,H}=\frac{2\ln T}{{\mu }_{\varphi }H}$ 与 NTK 特征值下界 ${\mu }_{\varphi }$ 相关联。

整体算法采用原始-对偶自然执行器-评论家框架。策略参数沿自然策略梯度方向更新：

其中 $w_k$ 通过最小化

得到。这里 $F(\theta )$ 是 Fisher 信息矩阵，$L(\theta ,\lambda )=J_{\theta }^r+\lambda J_{\theta }^c$ 是拉格朗日函数，$\lambda$ 是约束乘子。对偶变量通过梯度下降更新并投影到可行域：

其中 $\delta >0$ 是 Slater 条件保证的可行解差距。

实验与结果

需要说明的是，这是一篇纯理论论文，全文由问题设定、算法描述和严格的理论分析构成，不包含任何数值实验或基准测试。论文通过与已有理论结果的收敛率对比来展示方法的优势，核心论证完全依赖数学推导。

论文建立的主要理论结果如下：在满足分数函数有界、Fisher 非退化、策略参数化误差有界、评论家近似误差可控等标准假设下，取 $H_{\max }=T_{\max }=K=\Theta (T)$、$H_w=\Theta (\ln T)$、步长 $\alpha =\beta =1/\sqrt{K}$，算法可保证

其中 ${\epsilon }_{\text{bias}}$ 和 ${\epsilon }_{\text{app}}$ 分别来自策略参数化和评论家近似的误差。总期望样本成本为 $\tilde{\Theta }(T)$。

将这一结果与现有工作对比可以看出论文贡献的实质意义：Satheesh 等人在 2026 年的工作虽然也使用了神经评论家，但收敛率仅为 $\tilde{O}(T^{-1/4})$；Xu 等人在 2025 年的线性评论家结果虽然达到了 $\tilde{O}(T^{-1/2})$，但依赖于已知混合时间的假设。论文首次在神经评论家、平均奖励设定、无需混合时间三者同时成立的条件下达到 minimax 最优率。

讨论与可借鉴点

从方法论角度看，这项工作最值得借鉴的洞见在于将多水平蒙特卡洛的思想从采样层面扩展到优化层面。传统 MLMC 关注的是如何高效估计期望值，而论文发现优化迭代本身也可以被随机化——关键在于设计合适的分布使得去偏效果与样本成本之间达成有利权衡。这种"在优化迭代维度引入随机化"的思想可能对其他需要平衡偏差与计算成本的场景有所启发。

论文的另一个贡献在于消除了对混合时间的依赖。此前的原始-对偶方法往往需要通过样本丢弃或稀释来处理样本间的相关性，这要求事先知道或估计混合时间。HiMLMC 框架通过内层随机化自然地绕过了这一问题，使得理论保证不再依赖对系统动力学特性的先验知识。

当然，这项工作也存在局限。作为纯理论工作，算法的实际可行性、超参数敏感性以及常数因子大小都未经实验验证。NTK 分析依赖参数始终位于 NTK 球内的假设，这在实际深度网络训练中可能难以严格保证。此外，多层嵌套的随机化结构（两层几何分布、三层并行评论家更新）使得算法实现相对复杂，其在真实 CMDP 环境中的表现仍是开放问题。

摘要

约束马尔可夫决策过程（CMDP）为安全关键应用中的强化学习提供了一个自然的框架，在这类应用中，智能体在满足长期约束的同时最大化长期奖励。尽管基于线性评判器的原始-对偶执行器-评判器方法已得到充分理解，但将阶最优收敛保证推广到平均奖励CMDP中的神经评判器一直是一个悬而未决的问题。主要挑战在于神经评判器估计中一个基本的偏差-成本权衡：在神经切线核（NTK）分析下，降低评判器偏差会大幅增加评判器优化成本，从而阻碍原始-对偶框架中的阶最优收敛。我们通过引入一种分层多水平蒙特卡洛（MLMC）神经评判器来解决这一瓶颈，该评判器同时在轨迹采样和评判器优化两个层面执行去偏。由此得到的估计器以仅对数级的期望样本成本，达到了长时间评判器优化运行的偏差。基于该估计器，我们开发了一种原始-对偶自然执行器-评判器算法，该算法同时实现了阶为 $\tilde{O}(T^{-1/2})$ 的最优性差距和约束违反。这首次为具有一般策略参数化和神经评判器的无穷时域平均奖励CMDP建立了阶最优收敛保证，同时消除了需要已知底层混合时间的要求。即使在无约束设定下，我们的结果也是新颖的。

Abstract

Constrained Markov Decision Processes (CMDPs) provide a natural framework for reinforcement learning in safety-critical applications, where agents maximize long-term reward while satisfying long-term constraints. Although primal-dual actor-critic methods with linear critics are well understood, extending order-optimal convergence guarantees to neural critics in average-reward CMDPs has remained open. The main challenge is a fundamental bias-cost trade-off in neural critic estimation: under Neural Tangent Kernel (NTK) analysis, reducing critic bias substantially increases critic optimization cost, preventing order-optimal convergence in the primal-dual framework. We resolve this bottleneck by introducing a hierarchical Multilevel Monte Carlo (MLMC) neural critic that performs debiasing simultaneously across trajectory sampling and critic optimization. The resulting estimator attains the bias of a long critic optimization run with only logarithmic expected sample cost. Building on this estimator, we develop a primal-dual Natural Actor-Critic algorithm that achieves both an optimality gap and a constraint violation of order $\tilde{O}(T^{-1/2})$. This establishes the first order-optimal convergence guarantees for infinite-horizon average-reward CMDPs with general policy parameterization and neural critics, while eliminating the need to know the underlying mixing time. Our results are novel even in the unconstrained setting.

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

论文总结：平均奖励 CMDP 中阶最优神经 Actor-Critic 的分层多水平蒙特卡洛方法

1. 核心问题与研究动机

研究背景：约束马尔可夫决策过程（CMDP）是安全关键应用（如交通、通信网络、机器人、医疗）中强化学习的标准建模框架。这类问题需要在最大化长期平均奖励的同时满足长期约束。相较于折扣形式，平均奖励准则能更直接刻画稳态性能，特别适用于持续型决策任务。

已有进展的局限：

• 对于线性评判器的 primal-dual actor-critic 方法，已可获得 $\tilde{O}(T^{-1/2})$ 的阶最优收敛率（Xu et al. 2025；Mondal and Aggarwal 2024），匹配平均奖励 RL 的 minimax 样本复杂度下界（Jin and Sidford 2021）。
• 对于神经评判器，尽管基于神经切线核（NTK）的分析在折扣 MDP 中已获得 $\tilde{O}(T^{-1/2})$ 的阶最优结果（Ganesh et al. 2025），但平均奖励 CMDP 中目前的最优结果仅为 $\tilde{O}(T^{-1/4})$（Satheesh et al. 2026）。

根本性挑战：神经评判器估计中存在偏差-成本权衡。在 NTK 框架下，维持线性近似的投影导致评判器偏差的平方衰减速率与 MSE 相同。降低偏差需要显著增加评判器优化迭代次数，但在 primal-dual 嵌套循环架构下，每个外层迭代可承受的评判器计算有限，致使评判器平方偏差停留在 $\tilde{\Theta }(1)$，无法达到阶最优收敛所要求的 $\tilde{O}(T^{-1})$ 量级。这一瓶颈阻碍了现有神经 actor-critic 算法达到阶最优收敛。

2. 方法论

2.1 核心思想

论文提出分层多水平蒙特卡洛（HiMLMC）神经评判器，通过两层 MLMC 实现"双重去偏"：

• 外层 MLMC：随机化 critic 优化迭代次数，去除优化偏差；
• 内层 MLMC：随机化轨迹长度，去除采样偏差。

由此得到的估计器以仅 $O(\log T)$ 的期望样本成本，达到 $T$ 次 critic 优化运行的偏差水平。

2.2 算法：HiMLMC-PD-NAC

整体采用 primal-dual Natural Actor-Critic 框架：

其中 $\alpha ,\beta$ 为原始-对偶步长，$w_k$ 为 NPG 向量估计，${\eta }_{c,k}$ 为平均约束代价估计。

NPG 更新通过最小化：

其中 $F(\theta )$ 为 Fisher 信息矩阵，$L(\theta ,\lambda )=J_{\theta }^r+\lambda J_{\theta }^c$ 为拉格朗日函数。

2.3 评判器估计的关键公式

外层 MLMC 层：采样 $H_k\sim \text{Geom}(1/2)$，定义 $h_k=1+1\{2^{H_k}\le H_{\max }\}(2^{H_k}-1)$，构造：

内层 MLMC 层：采样 $U_{k,h}\sim \text{Geom}(1/2)$，定义 ${\ell }_{k,h}=1+1\{2^{U_{k,h}}\le T_{\max }\}(2^{U_{k,h}}-1)$，在长度 ${\ell }_{k,h}$ 的轨迹上构造梯度估计 ${\hat{v}}_{k,h}^{u,\text{MLMC}}$，进而执行带投影的 SGD 更新：

其中 ${\gamma }_{\xi ,H}=\frac{2\ln T}{{\mu }_{\varphi }H}$，$\mathcal{B}$ 为以初始化为中心的 NTK 球。

2.4 NPG 估计器（Algorithm 3）

类似地，对 Fisher 矩阵和策略梯度估计构造 MLMC 版本：

其中 ${\hat{X}}_{k,h}\in \{{\hat{F}}_{k,h},{\hat{g}}_{k,h}^u\}$，执行线性递推：

2.5 主要理论结果

定理 1（全局收敛与约束违反）：在假设 1–8 下，取 $m=H_{\max }$，$R=\Theta (\ln T)$，$H_{\max }=T_{\max }=K=\Theta (T)$，$H_w=\Theta (\ln T)$，$\alpha =\beta =1/\sqrt{K}$：

总期望样本成本为 $\tilde{\Theta }(T)$，无需已知混合时间。

3. 实验设计

本文为纯理论论文，未包含任何实验部分。全文由问题设定、算法描述、理论分析（定理与证明）、技术引理组成，没有 benchmark 数据集、没有对比方法、没有消融实验。

论文仅通过与已有理论结果的收敛率对比（表 1）展示相对优势，对比维度包括：

• 评判器类型（线性 ✗ vs 神经 ✓）；
• 收敛率与约束违反率；
• 是否需要已知混合时间。

4. 资源与算力

论文未提及任何计算资源（GPU 型号、数量、训练时长等）。作为理论分析论文，所有结论均通过数学推导得到，不涉及实际计算开销的具体测量。

5. 实验数量与充分性

无实验。论文不涉及数值模拟或真实环境验证。该工作的核心贡献是算法设计与理论收敛保证，所有有效性论证均依赖于：

1. 严格假设下的定理证明（定理 1–3、引理 1–8）；

2. 与已有理论结果的收敛率与假设对比（表 1）。

充分性讨论：对于理论性论文，这种形式是合理的——其说服力取决于证明的严谨性而非实验。然而，缺少实验验证也意味着所提算法（HiMLMC-PD-NAC）的实际可行性、超参数敏感性和常数因子大小未在实践中得到检验。

6. 主要结论与发现

1. 解决神经评判器偏差-成本权衡：提出的分层 MLMC 神经评判器以 $O(\log T)$ 的期望样本成本获得 $T$ 步优化才能达到的偏差。

2. 首次给出平均奖励 CMDP 神经评判器的阶最优保证：最优性差距与约束违反均为 $\tilde{O}(T^{-1/2})$，与 minimax 下界匹配，且总样本复杂度为 $\tilde{\Theta }(T)$。

3. 无需已知混合时间：算法与理论均不依赖于底层 CMDP 混合时间的先验知识，相比依赖样本稀释（sample thinning）或 MLMC 移除数据丢弃的方法更实用。

4. 无约束设定下亦属新颖：即使去掉约束（标准平均奖励 MDP），所建立的 $\tilde{O}(T^{-1/2})$ 神经评判器收敛结果同样为首创。

7. 优点

• 方法新颖性：首次将 MLMC 思想扩展到优化迭代维度的随机化，在轨迹采样去偏之外增加了优化去偏，构成"双层去偏"框架。
• 理论完整性：在 NTK 框架下给出严格的偏差-MSE 分解（Lemma 4、Theorem 3）、NPG 递推分析（Theorem 2）、拉格朗日误差界（Lemma 3）等完整证明链。
• 无需混合时间先验：通过 MLMC 自然消除对样本丢弃与混合时间估计的依赖，提升实际可用性。
• 架构普适性：覆盖了一般策略参数化、神经评判器、有约束 CMDP 三种特性的组合，达到 minimax 最优率。
• 清晰的对比定位：表 1 直观展示了在评判器类型、收敛率、混合时间需求三个维度上相对于现有工作的优势。

8. 不足与局限

• 缺乏实验验证：作为纯理论工作，未提供任何数值实验来验证算法在真实或仿真 CMDP 中的实际性能。常数因子、超参数选择（如 $H_{\max },T_{\max },H_w,R,m$）的敏感性与实用性未被检验。
• 依赖 NTK 假设：分析建立在网络参数始终位于 NTK 球内的假设上（需要半径 $R=\Theta (\ln T)$，投影 ${\Pi }_{\mathcal{B}}$），这在实际训练中可能较难维持；NTK 体制本身的特征化能力与现实深度网络行为存在差距。
• 依赖 Slater 条件：需要假设 2 提供的可行解差距 $\delta >0$，对偶步长与可行域均与 $\delta$ 相关。
• 依赖多个标准假设：包括分数函数有界且 Lipschitz（Assumption 4）、Fisher 非退化（Assumption 5）、策略参数化误差 ${\epsilon }_{\text{bias}}$（Assumption 6）、critic 近似误差 ${\epsilon }_{\text{app}}$（Assumption 7）、目标函数 $L$-光滑（Assumption 8）等，最终误差上界含 $\sqrt{{\epsilon }_{\text{bias}}}+\sqrt{{\epsilon }_{\text{app}}}$ 项。
• 算法复杂度较高：双层嵌套随机化（$H_k\sim \text{Geom}$、$U_{k,h}\sim \text{Geom}$）与三层并行的 vanilla-critic 更新（${\xi }_{k,u}^{(0)},{\xi }_{k,u}^{(1)},{\xi }_{k,u}^{(2)}$）使实际实现较为复杂，参数调优难度可能较高。
• 理论常数较粗：$\tilde{O}$ 符号掩盖了对数因子与混合时间 ${\tau }_{\text{mix}}$ 的依赖（实际收敛界含 ${\tau }_{\text{mix}}^2/\sqrt{T}$ 等项），对强混合（慢混合）问题的实际效率仍需进一步实证。

（完）