技术摘要：用于策略评估的具有时间差分学习的统计推断

问题陈述

本文解决了对强化学习（RL）中最优价值函数线性近似参数进行严格统计推断的挑战。具体而言，研究重点是采用 Polyak-Ruppert 平均的时间差分（TD）学习，这是一种广泛使用的策略评估算法。

虽然之前的研究已经确立了 TD 学习的有限样本一致性率和渐近高斯收敛性，但这些结果往往缺乏进行实际统计推断（例如构建置信区间或假设检验）所需的定量保证。现有的中心极限定理（CLT）结果通常是渐近性的，仅在样本量 $T$ 趋于无穷大且维度固定时成立，并未明确捕捉对维度 $d$ 或样本量 $T$ 的依赖关系。此外，现有的估计渐近协方差矩阵的方法通常存在计算复杂度高或缺乏有限样本误差界的问题。

作者在 独立同分布（i.i.d.）样本 的假设下研究了 TD 学习的统计特性，旨在弥合理论一致性与高维设置下实际有限样本统计推断之间的差距。

方法论

本文结合了高维概率理论、随机逼近分析和在线估计技术。

1. 算法设置： 研究考虑了带有 Polyak-Ruppert 平均的 TD 学习更新规则：
   $$\theta_t = \theta_{t-1} - \eta_t (A_t \theta_{t-1} - b_t)$$
   $$\bar{\theta}_T = \frac{1}{T} \sum_{t=1}^T \theta_t$$
   其中 $\{ (s_t, a_t, s'_t, r_t) \}$ 是 i.i.d. 样本，$A_t$ 和 $b_t$ 是由贝尔曼方程导出的瞬时矩阵和向量，$\eta_t = \eta_0 t^{-\alpha}$ 是多项式衰减的步长，其中 $\alpha \in (1/2, 1)$。

2. 高维 Berry-Esseen 界： 作者推导了缩放后的估计误差 $\sqrt{T}(\bar{\theta}_T - \theta^*)$ 的分布与高斯分布之间的凸距离的非渐近界。他们利用了通用的非线性 Berry-Esseen 界（Shao & Zhang, 2022），但针对 TD 学习矩阵（$A_t$ 和 $A$）的结构进行了专门的优化分析，以获得更紧致的速率。

3. 在线方差估计： 提出了一种新型的、计算高效的在线插件估计器 $\hat{\Lambda}_T$，用于估计渐近协方差矩阵 $\Lambda^*$。该估计器通过利用随迭代次数增加而增加的权重来递归更新，以反映 $\theta_t$ 不断提高的准确性，而无需存储完整的轨迹样本。

4. 高概率收敛： 作者推导了估计误差的欧几里得范数的高概率界，该界明确依赖于渐近方差的迹和维度，且不需要投影步骤来控制轨迹。

核心贡献

1. 更尖锐的高维 Berry-Esseen 界

作者建立了针对 TD 估计误差在凸集类上的新 Berry-Esseen 界。

• 速率： 通过选择步长衰减参数 $\alpha = 2/3$，他们实现了 $O(T^{-1/3})$ 的收敛速率。
• 改进： 这改进了 Samsonov 等人 (2024a) 在类似设置下得到的 $O(T^{-1/4})$ 的最佳已知速率。这种改进是通过对 TD 误差进行更具针对性的分解，以及对来自 TD 更新结构的特定矩阵项进行精细化处理实现的。
• 方差估计： 即使当真实的渐近方差被提出的在线估计器替代时，该界仍然成立，且估计的与真实的 Gaussian 分布之间的全变分距离以相同的 $O(T^{-1/3})$ 速率消失。

2. 新型在线协方差估计器

本文提出了一个计算高效的在线算法来估计渐近协方差矩阵 $\Lambda^*$。

• 复杂度： 该估计器需要 $O(Td^2 + d^3)$ 的时间以及 $O(d^2)$ 的空间，避免了需要 $O(T)$ 空间和 $O(T^{3/2})$ 时间的 Bootstrap 方法。
• 准确性： 估计器 $\hat{\Lambda}_T$ 收敛于 $\Lambda^*$，使得 $N(0, \hat{\Lambda}_T)$ 与 $N(0, \Lambda^*)$ 之间的全变分（TV）距离以 $O(T^{-1/3})$ 的速率消失。这确保了使用估计的方差进行推断不会降低收敛速率。

3. 更尖锐的高概率收敛保证

作者推导了估计误差 $\|\bar{\theta}_T - \theta^*\|_2$ 的高概率界，这些界：

• 在对数因子范围内与渐近方差相匹配。
• 在比先前文献更弱的条件下成立（例如，不需要投影步骤）。
• 明确依赖于渐近方差矩阵的迹 $\text{Tr}(\Lambda^*)$。
• 注：初始步长 $\eta_0$ 必须依赖于置信水平 $\delta$（具体为 $\eta_0 \sqrt{\log(1/(\delta \eta_0))} \leq C$），这是在当前设定下实现 Chernoff 式保证所必需的约束。

4. 有限样本统计推断

结合精炼的 Berry-Esseen 界和在线方差估计器，本文构建了：

• 置信区域： 用于 $\theta^*$ 的凸集（例如椭球体）。
• 同时置信区间： 用于 $\theta^*$ 单个分量的超矩形。
• 保证： 这些区域提供了保证的有限样本覆盖率，其向目标水平 $1-\delta$ 收敛的速率为 $O(T^{-1/3})$。据作者所知，这是第一个为 TD 模型参数提供此类有限样本覆盖率保证的正式统计推断程序。

结果

理论发现通过在一系列旨在难以区分的 MDPs 上进行的数值实验得到了证实。

• 收敛速率： 模拟确认，选择 $\alpha = 2/3$ 能使估计误差和分布近似的收敛速度最快，优于 $\alpha = 1/2$（先前工作中常用的参数）和 $\alpha = 1$。
• 分布近似： 缩放误差 $\sqrt{T}\bar{\Delta}_T$ 的经验分布按预测收敛到高斯极限 $N(0, \Lambda^*)$，且距离以理论速率下降。
• 覆盖率： 构建的置信区间随着 $T$ 的增加达到了目标 95% 的覆盖率，验证了有限样本推断框架。
• 误差分解： 实验将误差分解为初始化、采样和迭代组件，显示出采样误差在渐近意义上占主导地位，并与推导出的方差相一致。

重要性与声明

本文声称提供了在 i.i.d. 假设下，对于带有 Polyak-Ruppert 平均的 TD 学习统计推断的最尖锐已知理论速率。其主要意义在于：

1. 架起理论与实践的桥梁： 它超越了渐近解释，提供了用于构建置信区间的有限样本、非渐近保证，这是在安全关键或高风险应用中进行可靠策略评估的关键要求。
2. 计算效率： 通过引入一种避免了 Bootstrap 方法高计算和高内存成本的在线方差估计器，所提出的方法在处理高维问题时具有实际的可扩展性。
3. 速率的最优性： Berry-Esseen 界 $O(T^{-1/3})$ 的速率以及与之匹配的方差估计器速率，代表了对现有文献的最新进展，作者指出对于所选的步长计划，该速率似乎是紧致的。

作者承认其结果是在 i.i.d. 假设下推导的，这与更具挑战性的马尔可夫数据设定相比简化了分析，但他们认为这种简化的场景是一个必要的且具有挑战性的理论步骤，能够为更广泛的领域提供最尖锐的速率和见解。