技术摘要：弥合平均奖励与折扣 TD 学习之间的理论鸿沟

问题陈述

时序差分（TD）学习是强化学习的基石，然而其在平均奖励设定下的理论分析显著滞后于折扣设定。在折扣情形中，Bellman 算子是一个压缩映射，从而保证了解的唯一性和收敛分析的简洁性。相反，在平均奖励设定中，Bellman 算子关于任何范数都非压缩，且相应 Bellman 方程的解不唯一（仅定义至一个加性常数）。

现有处理平均奖励 TD 的文献相较于折扣情形存在若干局限性：

1. 限制性假设：许多方法需要假设（例如 $\Phi\theta \neq ce$），从而排除了表格（tabular）设定。
2. 收敛性保证：某些方法仅保证收敛至依赖于样本路径的不动点或集合，而非唯一、确定性的解。
3. 维度依赖性：收敛界通常包含参数维度 $d$ 的显式因子。
4. 条件数缩放：最先进的样本复杂度通常表现出对问题条件数的四次方依赖（$O(\eta^{-4})$），而折扣设定实现了二次方缩放（$O(\eta^{-2})$）。
5. 算法复杂度：在先前的工作中实现更好的缩放往往需要复杂的方差缩减技术（例如嵌套循环），偏离了标准 TD 的简洁性。

方法论

作者提出了一种在平均奖励设定下进行策略评估的新方法，通过将 Bellman 方程的解表述为一个约束优化问题。核心洞察在于：相对价值函数 $W^*$ 必须满足稳态约束（$\mu^\top W^* = 0$）。

1. 双链算法

为了解决投影 Bellman 方程 $W^* = \Pi T_\pi W^*$（其中 $\Pi = I - e\mu^\top$），作者推导了一个随机更新规则。该设定下随机逼近的一个关键挑战是“双重采样”问题：估计项 $\mu\mu^\top(R + W_t)$ 需要随机变量乘积的期望，由于相关性，无法从单条轨迹中估计。

为解决此问题，作者引入了一种双链算法，在每次迭代中利用两条独立的马尔可夫链（$\{s_t\}$ 和 $\{\hat{s}_t\}$）。

• 更新规则：参数向量 $\theta_t$ 使用两个分量进行更新：
  • $g(s_t, s'_t, \theta_t)$：估计标准 TD 误差项 $D(R + P\Phi\theta_t - \Phi\theta_t)$。
  • $f(s_t, \hat{s}_t, \theta_t)$：利用独立样本 $\hat{s}_t$ 打破相关性，估计约束项 $-\mu\mu^\top(R + \Phi\theta_t)$。
• 线性近似：通过将更新投影到特征空间，该方法推广到了线性函数近似（$W \approx \Phi\theta$）。

2. 单链算法

为了避免维护两条链的计算开销，作者提出了一种受梯度 TD（GTD）启发的单链算法。

• 机制：算法不采样第二个独立状态 $\hat{s}_t$，而是维护一个辅助变量 $w_t$ 来跟踪期望 $E[\phi(s)] = \Phi^\top\mu$。
• 更新：双链更新中的项 $\phi(\hat{s}_t)$ 被 $w_t$ 替换。变量 $w_t$ 通过单独的随机逼近步骤进行更新，以收敛至 $\Phi^\top\mu$。
• 权衡：虽然这将采样要求简化为单条轨迹，但分析表明，与双链变体相比，其对条件数的依赖性略差。

3. 理论框架：梯度分裂

收敛分析依赖于梯度分裂技术 [19]。作者证明，其算法的期望更新方向充当了特定复合二次函数的“梯度分裂”：
$$f(\theta) = \|\Phi(\theta - \theta^*)\|_{\text{Dir}}^2 + (\mu^\top\Phi(\theta - \theta^*))^2$$
这使得作者能够使用标准的随机梯度下降（SGD）递归技术来分析算法，尽管底层 Bellman 算子具有非压缩性。

主要贡献

本文声称通过同时实现以下特性，弥合了平均奖励与折扣 TD 学习之间的理论鸿沟：

1. 唯一、与样本无关的不动点：所提出的算法几乎必然收敛至单个确定性解 $\theta^*$，该解独立于随机轨迹和初始化。
2. 适用于表格和线性设定：分析同时适用于表格情形（其中 $\Phi = I$）和线性函数近似，无需限制性假设 $e \notin \text{span}(\Phi)$。
3. 与维度无关的界：收敛界不包含维度 $d$ 的显式因子（$\|\theta^*\|$ 或 $\|\theta_0\|$ 中固有的因子除外）。
4. 最后一次迭代收敛：结果保证针对最后一次迭代，与折扣 TD 中的标准一致，而非依赖于迭代平均。
5. 改进的条件数缩放：
   • 双链算法实现了 $\tilde{O}(\epsilon^{-1}\eta_1^{-2})$ 的样本复杂度，其中 $\eta_1$ 定义为 $\min_{\|x\|=1} (\|\Phi x\|_{\text{Dir}}^2 + (\mu^\top\Phi x)^2)$ 的条件数。这与折扣设定中观察到的二次方缩放相匹配。
   • 单链算法实现了 $\tilde{O}(\epsilon^{-1}\eta^{-4})$（四次方），这优于某些先前的工作，但略逊于双链变体。
6. 算法简洁性：实现了二次方缩放，且无需方差缩减技术（例如嵌套循环或周期性全批量），保持了普通 TD 更新的简洁性。

结果

作者为两种算法在独立同分布（i.i.d.）和马尔可夫采样下，以及常步长和衰减步长情形下，提供了有限样本分析。

• 理论界：定理 4.1–4.3 确立了收敛率和样本复杂度。双链方法在参数缩放方面与折扣 TD 的最先进水平相匹配。
• 数值实验：算法在来自 OpenAI Gym 和 MO-Gymnasium 的 15 个表格 MDP 上进行了测试。
  • 结果显示，所提出的方法在相对于真实解的近似误差方面，通常优于先前的基线方法（包括 [10], [11], [12], [17], [18] 和 [21]）。
  • 实验证实，这些方法收敛至唯一解，而某些基线方法（收敛至集合或依赖于样本的点）在表格设定中表现出更高的方差或误差。

意义

本文声称解决了与平均奖励 TD 分析相关的持久性理论缺陷。通过利用梯度分裂以及双链（或带辅助变量的单链）采样策略，作者证明了平均奖励 TD 可以实现与折扣 TD 同样有利的收敛性质：

• 唯一性：收敛至定义明确、唯一的解。
• 通用性：适用于表格和线性设定，无需限制性假设。
• 效率：对条件数具有二次方依赖，且无需复杂的方差缩减机制。

这项工作表明，平均奖励设定的理论困难可以通过将问题重构为约束优化任务，并利用特定的采样策略来处理 Bellman 算子的非压缩性来克服。