论在无局部时钟条件下差分时序差分学习的发散性

# 论无局部时钟的差分时序差分学习发散问题

来源: https://arxiv.org/html/2605.06874
David Antrobius 弗吉尼亚大学计算机科学系 [email protected] &Shangtong Zhang 弗吉尼亚大学计算机科学系 [email protected]

###### 摘要

学习率是强化学习（RL）的关键组成部分。本文通过全局时钟和局部时钟来区分两种类型的学习率。前者采用标准形式 $\alpha_t$，仅依赖于时间步 $t$（即全局时钟）。后者采用形式 $\alpha_{\nu(S_t,t)}$，其中 $\nu(s,t)$ 统计截至时间 $t$ 访问状态 $s$ 的次数（即局部时钟）。在折扣强化学习中，若一个 RL 算法在使用局部时钟时收敛，则在使用全局时钟时也必然收敛，反之亦然。据我们所知，目前尚未发现任何反例。本文的主要贡献在于证明这种良好的对应关系在平均奖励强化学习中不再成立。具体而言，我们构造了一个反例，表明尽管差分时序差分（differential TD）学习在使用局部时钟时是收敛的，但在使用全局时钟时可能会发散。这一反例解决了 Wan 等 (2021) 和 Blaser 等 (2026) 中提出的开放性问题。

## 1 引言

表型方法（Tabular method）是强化学习（RL, Sutton 和 Barto (2018)）中的一类基础算法。回顾表型 RL 的历史，我们可以发现一个清晰的模式：早期对表型 RL 方法的理论分析通常在学习率中使用局部时钟。此处，学习率中的局部时钟指形式为 $\alpha_{\nu(S_t,t)}$ 的学习率，其中 $\nu(s,t)$ 统计截至时间 $t$ 访问状态 $s$ 的次数。这与使用全局时钟的学习率形成对比，后者形式为 $\alpha_t$，仅依赖于时间步 $t$。全局时钟指学习率中的时间步 $t$，而局部时钟指学习率中依赖于状态的访问计数 $\nu(s,t)$。例如，经典 Q-学习（Q-learning）的收敛性证明通常使用局部时钟（Watkins, 1989; Watkins 和 Dayan, 1992; Jaakkola 等, 1993; Tsitsiklis, 1994; Bertsekas 和 Tsitsiklis, 1996）。

我们认为，理论分析中使用局部时钟主要是出于技术便利。Borkar (2009) 的第 7 章详细阐述了局部时钟在随机逼近算法收敛性分析中的作用。直观地说，局部时钟允许在不同状态间进行更均衡的更新，本质上将 RL 中的马尔可夫样本转化为独立同分布（i.i.d.）样本，从而大大简化了分析。然而，局部时钟并非实践者的首选。例如，整本教材 Sutton 和 Barto (2018) 既未提及也未在学习率中使用任何局部时钟。大多数实践者更倾向于使用全局时钟。

这种理论研究者与实践者之间的差距在折扣强化学习设置中并不构成问题。尽管早期对折扣 RL 方法的理论分析经常使用局部时钟，但近期的研究表明，相同的算法在使用全局时钟时也是收敛的。例如，使用全局时钟的 Q-学习的收敛性已由 Lee 和 He (2020); Chen 等 (2024); Liu 等 (2025a) 建立。据我们所知，目前尚无已知的反例表明在折扣 RL 中，某个在使用局部时钟时收敛的算法在使用全局时钟时会发散。

在平均奖励强化学习中，早期的理论分析（如 RVI Q-学习）同样在学习率中使用局部时钟（Abounadi 等, 2001）。开创性工作 Wan 等 (2021) 为平均奖励 RL 开发了一套新的时序差分算法，消除了 RVI Q-学习中对参考状态的需求。Wan 等 (2021) 中的离策略（off-policy）策略评估算法被称为差分 TD。而 Wan 等 (2021) 中的控制算法被称为差分 Q-学习。在 Wan 等 (2021) 的主文中，这两种算法均在学习率中使用全局时钟呈现。然而，在附录的收敛性分析中，这两种算法仅被证明在使用局部时钟时收敛。因此，开放性的问题是：这些算法在学习率中使用全局时钟时是否也收敛？Blaser 等 (2026) 部分回答了这个问题，他们表明当 $\eta$ 足够小时，即使使用全局时钟，差分 TD 也是收敛的。这里 $\eta$ 是差分 TD 中的一个超参数，我们将在后文介绍。然而，仍然存在差距，因为 Wan 等 (2021) 表明在使用局部时钟时，对于任意 $\eta > 0$，差分 TD 都是收敛的。那么对于任意 $\eta > 0$，使用全局时钟的差分 TD 是否也收敛？这是 Blaser 等 (2026) 中留下的一个开放性问题。

人们可能会乐观地推测上述问题的答案是肯定的。毕竟在折扣强化学习设置中，我们观察到在使用局部时钟时收敛的算法在使用全局时钟时也是收敛的。据我们所知，文献中没有任何反例。本文的关键贡献在于证明这种良好的对应关系在平均奖励强化学习中不再成立。特别是，我们构造了一个反例，表明差分 TD 在使用全局时钟时可能会发散。这一负面结果令人惊讶且有趣，因为它表明在平均奖励设置中，学习率的选择对 RL 算法收敛性的影响可能比在折扣设置中更为显著。

## 2 背景

我们考虑一个由元组 $(\mathcal{S}, \mathcal{A}, p, p_0, r)$ 定义的无限视界马尔可夫决策过程（MDP, Bellman (1957)），其中 $\mathcal{S}$ 是有限状态空间，$\mathcal{A}$ 是有限动作空间，$p: \mathcal{S} \times \mathcal{S} \times \mathcal{A} \to [0, 1]$ 是转移函数，$p_0: \mathcal{S} \to [0, 1]$ 是初始状态分布，$r: \mathcal{S} \times \mathcal{A} \to \mathbb{R}$ 是奖励函数。在时间步 0，初始状态 $S_0$ 从 $p_0$ 中抽取。在每一步 $t \geq 0$，根据策略 $\pi: \mathcal{A} \times \mathcal{S} \to [0, 1]$ 选择动作 $A_t$，即 $A_t \sim \pi(\cdot | S_t)$。随后发出奖励 $R_{t+1} = r(S_t, A_t)$，并从 $p(\cdot | S_t, A_t)$ 中抽取下一个状态 $S_{t+1}$。

在折扣强化学习设置中，我们考虑折扣因子 $\gamma \in [0, 1)$。策略评估的目标是估计给定策略 $\pi$ 的价值函数，定义为 $v_\pi(s) \doteq \mathbb{E}[\sum_{i=0}^\infty \gamma^i R_{t+i+1} | S_t = s]$。在平均奖励强化学习设置中，我们考虑平均奖励 $J_\pi \doteq \lim_{T \to \infty} \frac{1}{T} \mathbb{E}[\sum_{t=0}^{T-1} R_{t+1}]$，并关注策略 $\pi$ 的差分价值函数，定义为 $\bar{v}_\pi(s) \doteq \mathbb{E}[\sum_{i=0}^\infty (R_{t+i+1} - J_\pi) | S_t = s]$。在温和条件下，$J_\pi$ 独立于 $S_0$。

时序差分（TD）学习是 RL 中策略评估最基础的一类算法。在本文中，我们考虑离策略 TD，其中数据由行为策略 $\mu$ 生成（即 $A_t \sim \mu(\cdot | S_t)$），而我们希望估计另一个目标策略 $\pi$ 的价值函数。在折扣设置中，TD 更新由下式给出：

$$
\delta_t = R_{t+1} + \gamma v_t(S_{t+1}) - v_t(S_t), \quad (1)
$$

$$
v_{t+1}(s) = 
\begin{cases} 
v_t(s) + \alpha_t \rho_t \delta_t, & \text{若 } s = S_t, \\
v_t(s), & \text{其他情况},
\end{cases} \quad (2)
$$

其中 $\rho_t = \frac{\pi(A_t | S_t)}{\mu(A_t | S_t)}$ 是重要性采样比率。这里，$\alpha_t$ 是学习率，例如 $\alpha_t = \frac{1}{t+1}$，我们将式 (1) 称为*带有全局时钟的折扣 TD*。令 $\nu(s, t) \doteq \sum_{i=0}^t \mathbb{I}\{S_i = s\}$ 为截至时间 $t$ 状态 $s$ 被访问的次数，其中 $\mathbb{I}$ 为指示函数。如果我们在式 (1) 中将 $\alpha_t$ 替换为 $\alpha_{\nu(S_t, t)}$，我们就得到*带有局部时钟的折扣 TD*。众所周知，在标准假设下（例如，由 $\mu$ 诱导的马尔可夫链是遍历的，$\pi$ 关于 $\mu$ 绝对连续，且 $\alpha_t$ 满足 Robbins-Monro 条件），带有两种时钟的折扣 TD 都是收敛的。

Wan 等 (2021) 将离策略 TD 扩展到平均奖励设置，并提出了以下差分 TD 的更新规则：

$$
\delta_t = R_{t+1} - \hat{J}_t + v_t(S_{t+1}) - v_t(S_t), \quad (3)
$$

$$
\hat{J}_{t+1} = \hat{J}_t + \alpha_t \eta \rho_t \delta_t, \quad (4)
$$

$$
v_{t+1}(s) = 
\begin{cases} 
v_t(s) + \alpha_t \rho_t \delta_t, & \text{若 } s = S_t, \\
v_t(s), & \text{其他情况},
\end{cases} \quad (5)
$$

其中 $\eta > 0$ 是一个超参数，$\{\hat{J}_t\}$ 是平均奖励 $J_\pi$ 的估计值。我们将式 (3) 称为*带有全局时钟的差分 TD*。类似地，通过将式 (3) 中出现的 $\alpha_t$ 全部替换为 $\alpha_{\nu(S_t, t)}$，我们得到*带有局部时钟的差分 TD*。Wan 等 (2021) 在其附录中证明了对于任意 $\eta > 0$，带有局部时钟的差分 TD 几乎处处收敛，尽管他们的主文中仅呈现了带有全局时钟的差分 TD，且完全未提及局部时钟。Blaser 等 (2026) 表明，当 $\eta$ 足够小时，带有全局时钟的差分 TD 也是收敛的。因此，对于不够小的 $\eta$，带有全局时钟的差分 TD 是否收敛仍是一个开放性问题。令人惊讶的是，我们将在本文中指出答案是否定的。

现在我们介绍一些矩阵分析的定义。

###### 定义 2.1.

如果矩阵 $A$ 可以表示为 $A = sI - B$，其中 $s > 0$，$B \geq 0$（即 $B$ 的所有元素非负），且 $s \geq \rho(B)$（$\rho(B)$ 为 $B$ 的谱半径），则称 $A$ 为 $M$-矩阵。

###### 定义 2.2.

如果矩阵 $A$ 的所有特征值都具有严格正的实部，则称 $A$ 为正稳定（positive stable）。如果 $-A$ 是正稳定的，则称 $A$ 为赫尔维茨（Hurwitz）矩阵。

## 3 差分 TD 与折扣 TD 有何不同？

我们现在提供一些必要的背景知识，以说明折扣 TD 和差分 TD 与全局时钟和局部时钟相互作用方式的根本区别。这主要归功于 Blaser 等 (2026)，我们在此提供细节仅为了完整性，并为下一节中的反例奠定基础。

ODE 方法是建立 RL 算法几乎处处收敛性的有力工具。以带有局部时钟的折扣 TD 为例。为了应用 ODE 方法，我们研究与带有局部时钟的折扣 TD 相关的 $\text{ODE}_\infty$，其形式为：

$$
\frac{dx(t)}{dt} = -(I - \gamma P_\pi) x(t), \quad (6)
$$

其中 $I$ 是单位矩阵，$P_\pi$ 是在策略 $\pi$ 下的转移矩阵，即 $P_\pi(s, s') = \sum_a \pi(a | s) p(s' | s, a)$。标准的 ODE 方法（例如，Borkar (2009); Borkar 等 (2025); Liu 等 (2025a)）需要验证上述 ODE 是全局渐近稳定的（GAS），且 0 是其唯一的平衡点。幸运的是，这里确实如此，因为 $I - \gamma P_\pi$ 是非奇异 $M$-矩阵。众所周知，非奇异 $M$-矩阵是正稳定的（Plemmons, 1977）。与带有全局时钟的折扣 TD 相关的 $\text{ODE}_\infty$ 则是：

$$
\frac{dx(t)}{dt} = -D_\mu (I - \gamma P_\pi) x(t), \quad (7)
$$

其中 $D_\mu$ 是对角矩阵，满足 $D_\mu(s, s) = d_\mu(s)$，且 $d_\mu$ 是由 $\mu$ 诱导的马尔可夫链的平稳分布。假设由 $\mu$ 诱导的马尔可夫链是不可约的，则对所有 $s$ 有 $d_\mu(s) > 0$。因此 $D_\mu$ 也是正稳定的。已知非奇异 $M$-矩阵左乘正稳定对角矩阵后仍为正稳定（Fiedler 和 Pták, 1962; Plemmons, 1977），这意味着 $D_\mu (I - \gamma P_\pi)$ 也是正稳定的，因此与带有全局时钟的折扣 TD 相关的 $\text{ODE}_\infty$ 也是 GAS 的。这两个 ODE 之间的差异是直观的。使用局部时钟时，所有状态以相同的“量级”进行更新，因此实际的采样分布无关紧要。但使用全局时钟时，状态根据其被访问的频率以不同的量级进行更新。因此，存在一项 $D_\mu$ 来捕捉采样分布。

对于带有局部时钟的差分 TD，相应的 $\text{ODE}_\infty$ 为：

$$
\frac{dx(t)}{dt} = -(I - P_\pi + \eta ee^\top) x(t), \quad (8)
$$

其中 $e$ 是全 1 向量。详细推导可在 Wan 等 (2021) 中找到。虽然...