Near-Optimal Sample Complexity Bounds for Constrained Average-Reward MDPs

技术摘要：约束平均奖励 MDP 的近最优样本复杂度界限

问题定义
本文研究了在生成模型下，学习约束平均奖励马尔可夫决策过程（CAMDP）中 $\epsilon$-最优策略的样本复杂度。CAMDP 由元组 $\mathcal{M} = \langle S, A, P, r, c, b, s \rangle$ 定义，其中智能体旨在最大化稳态平均奖励 $\rho^\pi_r(s)$，同时满足平均约束 $\rho^\pi_c(s) \geq b$。基准策略 $\pi^*$ 是平稳确定性策略的外部混合。作者考虑了两种可行性机制：

1. 松弛可行性（Relaxed Feasibility）： 输出策略对约束的违反程度最多为 $\epsilon$（即 $\rho^{\hat{\pi}}_c(s) \geq b - \epsilon$）。
2. 严格可行性（Strict Feasibility）： 输出策略必须精确满足约束（即 $\rho^{\hat{\pi}}_c(s) \geq b$）。
   分析依赖于结构参数：$S$ 和 $A$（状态和动作计数）、$H$（奖励和约束函数的偏差跨度一致上界）、$B$（瞬态时间的一致上界）以及 $\zeta$（Slater 裕度下界，表征可行区域的大小）。本文假设满足策略级折扣方差条件（假设 1）。

方法论
作者提出了一种基于模型的原对偶算法（算法 1），该算法通过求解一系列扰动的经验折扣 MDP 来运行。关键方法论组件包括：

• 原对偶框架（Primal-Dual Framework）： 算法维护一个拉格朗日乘子 $\lambda_t$，并根据当前策略的约束违反情况来更新它。原问题步骤通过在经验折扣设置下求解最大化拉格朗日奖励 $r_p + \lambda_t c$ 的确定性策略 $\hat{\pi}_t$。
• 扰动与舍入（Perturbation and Rounding）： 为了确保最优动作的唯一性并便于集中性分析，奖励信号通过随机变量 $Z$ 进行扰动。拉格朗日乘子在网格 $\Lambda$ 上进行离散化。
• 跨信号集中性（Cross-Signal Concentration）： 一个核心技术贡献是针对有限族经验拉格朗日 Oracle 策略的新型集中性定理（定理 2）。不同于对整个策略类进行标准的一致集中性分析，该结果控制了算法生成的特定策略的估计误差。它利用“状态-动作吸收构造”来解耦行，并采用条件 Bernstein 层级结构以保留依赖于实例的方差项。
• 向平均奖励转移（Transfer to Average Reward）： 通过桥接引理（bridge lemmas）将为扰动折扣问题导出的保证转移到原始的平均奖励问题，这些引理通过偏差跨度 $H$ 将折扣值与平均奖励联系起来。

主要贡献与结果
本文建立了 CAMDP 在平均奖励设置下的第一个近最优样本复杂度界限，并区分了松弛可行性和严格可行性：

1. 松弛可行性上界： 该算法在松弛约束满足条件下实现 $\epsilon$-最优策略，其样本复杂度为 $\tilde{O}\left(\frac{SA(B + H)}{\epsilon^2}\right)$。值得注意的是，该速率与 Slater 裕度 $\zeta$ 无关。
2. 严格可行性上界： 对于严格约束满足，样本复杂度增加至 $\tilde{O}\left(\frac{SA(B + H)}{\epsilon^2 \zeta^2}\right)$。对 $\zeta^{-2}$ 的依赖反映了在不产生违反的情况下确保精确可行性的难度。
3. 下界：
   • 对于弱通信（weakly communicating） CAMDP，作者构造了一个直径为 $D$（其中 $H = \Theta(D)$）的困难族，证明了严格可行性的自适应极小极大下界为 $\tilde{\Omega}\left(\frac{SAH}{\epsilon^2 \zeta^2}\right)$。
   • 对于一般（general） CAMDP，一个单独的瞬态困难族在平衡采样下给出了下界 $\tilde{\Omega}\left(\frac{SAB}{\epsilon^2 \zeta^2}\right)$。
   • 结合这些子族，平衡算法的最坏情况复杂度下界为 $\tilde{\Omega}\left(\frac{SA(B + H)}{\epsilon^2 \zeta^2}\right)$，这在严格可行性上界方面与之一匹配（仅差对数因子）。

意义与主张
作者声称这项工作提供了 CAMDP 在平均奖励设置下的第一个样本复杂度特征描述。结果表明，学习长程约束下的统计难度由偏差跨度（$H$）、瞬态行为（$B$）和可行域裕度（$\zeta$）共同决定。

论文明确指出，虽然松弛和严格可行性在折扣 CMDP 中已有研究（例如 Vaswani 等人，2022），但平均奖励设置呈现出独特的挑战，因为诸如 Bellman 收缩等性质并不成立。通过建立匹配的上界和下界，本研究证明了严格可行性所需的额外 $\zeta^{-2}$ 依赖是不可避免的，并确立了松弛机制与严格机制之间的可证明分离。所提出的算法和分析框架被认为是第一个在生成模型下实现约束平均奖励强化学习近极小极大最优性的工作。