异步类别分布型时序差分学习的有限迭代理论

# 异步分类分布型时序差分学习的有限迭代理论

**来源:** https://arxiv.org/html/2605.06866

**作者:** Ege C. Kaya, Abolfazl Hashemi  
**单位:** 普渡大学埃尔莫尔家族电气与计算机工程学院 (Elmore Family School of Electrical and Computer Engineering, Purdue University)  
**地址:** 美国印第安纳州西拉法叶市，邮编 47906  
**邮箱:** [email protected], [email protected]

###### 摘要

近期的非渐近分析极大地推进了分布型策略评估的理论，但这些研究主要关注生成模型下的同步全状态更新、基于模型的估计器、加速变体或不同的近似架构。标准的分类时序差分（Temporal-Difference, TD）学习通常应用于不同的场景：它在每次迭代中异步地执行单状态更新，并且在在线设置下由马尔可夫轨迹驱动。这使得现有的有限迭代理论与最贴近实际分布型时序差分实现的分类递归之间留下了一个重要的空白。

本文针对两种分类策略评估方法填补了这一空白：Cramér 几何下的标量分类时序差分学习，以及最大均值差异（Maximum Mean Discrepancy, MMD）几何下的多元符号分类时序差分学习。在合适的等距嵌入之后，这两种算法均表现为异步单状态随机逼近（Stochastic Approximation, SA）递归，并在逐状态上确范数下具有收缩性。这使得我们在独立同分布（i.i.d.）和马尔可夫状态采样下的折扣问题中，以及在独立同分布 episodically 采样下的无折扣固定视界问题中，都能提供有限迭代保证。

## 1 引言

分类表示是分布型强化学习（RL）中核心的近似族之一\[4, 39, 15, 14, 51, 30, 40, 5\]。在标量情况下，它们构成了由 C51 发起的分类方法的基础\[4\]；而在多元情况下，它们支持向量回报的符号测度构造\[49\]。这些方法用有限维对象替换无限维的回报分布对象，同时保留了支配投影分布型策略评估的几何结构\[21, 23, 24, 43, 32\]。

对于这些分类方法，渐近图景目前已得到充分理解\[20, 17, 47, 22, 6, 28, 39, 5\]。标量分类时序差分（CTD）方法在 Cramér 度量下允许投影贝尔曼收缩，并具有渐近保证\[39, 5\]。多元符号分类时序差分（MTD）方法则允许类似的基于最大均值差异（MMD）的收缩及理论\[49\]。然而，这些 TD 方法的有限迭代行为尚不如渐近行为那样清晰。这一点至关重要，因为标准 TD 学习并非同步全状态过程\[46, 45, 48, 10\]。在实践中，每次更新仅修改被采样的状态，而在在线 RL 中，采样状态由马尔可夫轨迹生成。因此，针对异步、轨迹驱动更新的有限迭代保证，是理解 CTD 和 MTD 在实际相关场景中逼近其投影不动点速度的自然基准。

若干近期成果解决了邻近的有限迭代问题\[37, 7, 44, 34, 16, 36, 8, 52, 41, 35\]。这些工作确立了非渐近分布分析是可行的，但并未为驱动单状态更新的标准异步分类递归提供有限迭代理论。

本文分为两个部分。第一部分处理在 i.i.d. 和马尔可夫采样下的折扣策略评估，其框架受 Chen 等人\[12, 13, 11\]、Robbins 和 Monro \[38\]、Ljung \[29\]、Borkar \[9\] 以及 Kushner 和 Yin \[26\] 的启发。第二部分处理无折扣策略评估的一个易处理实例，即在有限、固定视界的 Episodic 场景中。在这两部分中，主要主题保持一致：在合适的逐状态等距嵌入后，CTD 和 MTD 构成块上确范数几何下的异步随机逼近（SA）递归。

**采样机制的实际解释。** 本文考虑的每种采样模型都有其实际的 RL 解释。折扣 i.i.d. 场景指向基于回放或生成模型的基准，其中更新由从缓冲区或模拟器中抽取的近似独立样本形成，这也类似于常用于理论研究 TD 风格方法的同步分析。折扣马尔可夫场景是 TD 学习的标准在线设置，其中样本沿单一行为轨迹顺序生成。在固定视界无折扣情况下，Episodic 场景是固定视界 RL 的标准基于重置的公式化，其中交互进行固定视界 $H$，然后从初始分布重新开始。

**主要观点：** 我们的主要主张是，一旦将 CTD 和 MTD 写入正确的逐状态嵌入中，这些更新规则就变成了具有收缩结构的异步 SA 递归，从而能够实现有限迭代控制。

**贡献：**
1. 我们建立了在折扣 i.i.d. 和马尔可夫采样下异步 CTD 和 MTD 的有限迭代保证。
2. 我们建立了在无折扣固定视界 i.i.d. Episodic 采样下 CTD 和 MTD 的有限迭代保证。
3. 我们记录了一个确定性表示误差分解，将投影不动点界转化为包含显式投影偏差项的总误差界。

## 2 相关工作

两条研究线索最直接相关。在有限迭代方面，Chen 等人 \[12, 13, 11\] 在 i.i.d. 和马尔可夫采样下为收缩递归开发了非渐近 SA 工具，建立在更广泛的 TD 和 SA 文献之上 \[7, 37, 38, 29, 9, 26\]。在分布方面，Rowland 等人 \[39\] 和 Bellemare 等人 \[5\] 建立了支撑 CTD 的标量分类投影和 Cramér 收缩理论，而 Wiltzer 等人 \[49\] 为 MTD 提供了多元符号分类 MMD 框架。对于无折扣部分，我们的设置遵循 De Asis 等人 \[18\] 的固定视界观点。我们的贡献是将这些线索结合起来，用于实践中使用的表格异步分类递归，而不是用于同步或理想化的替代方案。

近期的非渐近分布分析研究了几种邻近的场景。Peng 等人 \[36\] 和 Böck 与 Heitzinger \[8\] 分析了具有生成模型访问权限的 CTD，其中更新是同步或加速的。Zhang 等人 \[52\] 和 Rowland 等人 \[41\] 研究了具有更强采样访问权限的基于模型或直接估计的程序。Wu 等人 \[50\] 关注离线策略评估，Peng 等人 \[35\] 研究线性函数近似，Kastner 等人 \[25\] 考虑了基于不同散度和渐近重点的 KL 分类分析。相比之下，我们分析的是 CTD 和 MTD 的精确异步递归。

## 3 折扣分类策略评估

我们考虑一个折扣马尔可夫决策过程 \[45\] $(\mathcal{S}, \mathcal{A}, P, R, \gamma)$，具有有限状态空间 $\mathcal{S}$，有限动作空间 $\mathcal{A}$，奖励函数 $R(s, a)$，转移核 $P(\cdot \mid s, a)$ 以及折扣因子 $\gamma \in (0, 1)$。我们假设在标量情况下 $R: \mathcal{S} \times \mathcal{A} \to [0, 1]$，而在多元情况下 $R: \mathcal{S} \times \mathcal{A} \to [0, 1]^q, q \geq 2$。策略 $\pi$ 全程固定。诱导的状态轨迹要么是具有分布 $\rho$ 的 i.i.d.，要么是平稳分布为 $\mu_{\mathcal{S}}$ 的马尔可夫链。在马尔可夫情况下，我们假设不可约性和非周期性。$\mathcal{S}$ 的有限性意味着由固定策略 $\pi$ 下的 MDP 产生的马尔可夫链几何混合 \[27\]，即存在常数 $C_{\mathrm{mix}} \geq 1$ 和 $\sigma_{\mathrm{mix}} \in (0, 1)$ 使得对于所有 $k \geq 0$：

$$
\sup_{x \in \mathcal{S}} \left\| \Pr(S_k \in \cdot \mid S_0 = x) - \mu_{\mathcal{S}}(\cdot) \right\|_{\mathrm{TV}} \leq C_{\mathrm{mix}} \sigma_{\mathrm{mix}}^k \quad \text{(1)}
$$

对于 $\delta > 0$，我们定义相关的混合时间 $t_\delta := \min \{ k \geq 0 : \sup_{x \in \mathcal{S}} \| \Pr(S_k \in \cdot \mid S_0 = x) - \mu_{\mathcal{S}}(\cdot) \|_{\mathrm{TV}} \leq \delta \}$ \[2\]。

对于 CTD 和 MTD，我们使用块上确范数收缩度量 $\ell_\infty$，它允许到具有收缩范数 $\|\cdot\|_{2,\infty}$ 的乘积空间的逐状态等距嵌入 $\mathcal{I}$，以及到支撑为 $\Theta$ 的状态索引表示空间 $\mathcal{F}^{\mathcal{S}}_\Theta$ 的逐状态投影 $\Pi^\Theta$。然后我们可以组合分布型贝尔曼算子 $T^\pi$ 以获得嵌入的投影算子 $\mathcal{O} := \mathcal{I} \circ \Pi^\Theta T^\pi \circ \mathcal{I}^{-1}$ \[3\]。该算子具有一个单步采样贝尔曼目标 $\widehat{T}(U_k; s, (R_k, S_{k+1}))$，由当前估计 $U_k$ 和随机样本 $(R_k, S_{k+1})$ 计算得出，满足：

$$
\mathbb{E}[\widehat{T}(U_k; S_k, (R_k, S_{k+1})) \mid U_k, S_k = s] = (\mathcal{O}U_k)(s) \quad \text{(4)}
$$

并且递归形式为：

$$
U_{k+1} = U_k + \alpha_k P_{S_k} (\widehat{T}(U_k; S_k, (R_k, S_{k+1})) - U_k(S_k)) \quad \text{(5)}
$$

其中对于每个 $s \in \mathcal{S}$，$P_s$ 表示到块 $s$ 的坐标投影器。折扣分析的重点是，精确的单状态递归已经具备了有限迭代 SA 界所需的要素。具体而言，证明使用了平均算子在 $\|\cdot\|_{2,\infty}$ 下的收缩性，基于 $\|\cdot\|_{2,p}$ 的 $\|\cdot\|_{2,\infty}$ 的 Moreau 包络平滑 \[9, 26, 3, 31, 2\]，根据方法不同采用仿射条件二阶矩界或中心路径扰动界，单步目标映射在 $\|\cdot\|_{2,\infty}$ 下的逐样本 1-Lipschitz 连续性，以及马尔可夫情况下的几何混合。更准确地说，令 $p^\star := \max \{2, \lceil \log |\mathcal{S}| \rceil\}$，平滑论证通过平方块上确范数距离的广义 Moreau 包络 $M_{\vartheta, p^\star}$ 引入参数 $\vartheta > 0$。关于这些共同要素的更多细节推迟到附录 A \[A1\]，而 CTD 和 MTD 的折扣有限迭代结果的正式验证分别推迟到附录 B \[A2\] 和 C \[A3\]。

### 3.1 折扣 CTD

对于每个状态 $s \in \mathcal{S}$，固定一个有序支撑集 $\Theta(s) = \{\theta_1(s) < \dots < \theta_d(s)\} \subset \mathbb{R}$。$\mathcal{F}^{\mathcal{S}}_{\mathrm{C},\Theta}$ 是支持在这些逐状态网格上的状态索引分类律的类。收缩度量 $\ell_{\mathrm{C},\infty}$ 是上确 Cramér 度量，嵌入 $\mathcal{I}_{\mathrm{C}}$ 是应用于所有状态的标准累积质量等距 $\mathcal{I}_{\mathrm{C},s}$ \[39, 5\]，而逐状态投影 $\Pi_{\mathrm{C}}^\Theta$ 是应用于所有状态的通常线性插值分类投影 $\Pi_{\mathrm{C}}^{\Theta(s)}$。给定采样转移 $(S_k, A_k, R_k, S_{k+1})$，采样贝尔曼目标为：

$$
\widehat{T}_{\mathrm{C}}(U_k; S_k, (R_k, S_{k+1})) := \mathcal{I}_{\mathrm{C},S_k} \Bigl( \Pi_{\mathrm{C}}^{\Theta(S_k)} \bigl( (f_{R_k,\gamma})_\# \mathcal{I}_{\mathrm{C},S_{k+1}}^{-1}(U_k(S_{k+1})) \bigr) \Bigr)
$$