技术摘要：Q-MMR：通过递归重加权与矩匹配进行离线策略评估

1. 问题陈述

本文解决了有限 horizon 马尔可夫决策过程（MDP）中的离线策略评估（OPE）问题。其目标是利用从行为策略 $\pi_D$ 收集的数据集，估计目标策略 $\pi$ 的期望回报 $J(\pi)$。该设定涉及通用函数近似（GFA），即使用函数类 $\mathcal{F}$ 来建模目标策略的 Q 函数 $Q^\pi$。

作者指出了现有 OPE 文献中两个主要的理论缺口：

1. 维度依赖性：GFA 的标准分析（例如拟合 Q 评估 FQE）通常产生的误差界依赖于函数类的统计复杂度（例如 $\log |\mathcal{F}|$ 或覆盖数）。这种依赖性通常是松散的，特别是在在线策略设定中，蒙特卡洛估计是无维度的。
2. 与线性/表格分析的不一致性：针对线性和表格设定（通常在仅满足可实现性的条件下）存在精细的、无维度的保证，但这些结果无法自然地推广到通用函数类。此外，线性分析通常依赖于比 GFA 分析所需的贝尔曼完备性假设更弱的条件（即可实现性）。

2. 方法论：Q-MMR

作者提出了Q-MMR（基于 Q 函数的矩匹配重加权），这是一种新颖的算法框架，它以自顶向下的归纳方式学习一组标量权重，每个数据点对应一个权重。

算法概述

给定 $n$ 个独立同分布（i.i.d.）的轨迹和函数类 $\mathcal{F} = \{\mathcal{F}_h\}_{h=1}^H$：

1. 初始化：将所有数据点 $i$ 的权重设为 $w^{(i)}_0 \equiv 1$（因为初始状态 - 动作对是固定的）。
2. 递归重加权：对于每个时间步 $h = 1$ 到 $H$，算法通过求解一个极小极大优化问题来学习权重向量 $w^{[n]}_h = \{w^{(i)}_h\}_{i=1}^n$：
   $$\hat{w}^{[n]}_h = \arg\min_{w^{[n]}_h} \sup_{f \in \mathcal{F}_h} \left| \frac{1}{n} \sum_{i=1}^n w^{(i)}_h f(s^{(i)}_h, a^{(i)}_h) - \frac{1}{n} \sum_{i=1}^n \hat{w}^{(i)}_{h-1} f(s^{(i)}_h, \pi) \right|$$
   该目标函数通过积分概率度量（Integral Probability Metric）最小化当前状态 - 动作对的重新加权分布与目标策略下下一状态的重新加权分布之间的差异。
3. 估计：回报的最终估计是重新加权的奖励总和：
   $$\hat{J}(\pi) = \frac{1}{n} \sum_{i=1}^n \sum_{h=1}^H w^{(i)}_h r^{(i)}_h$$

关键设计选择

• 非参数权重：与学习权重参数化函数的边际重要性采样（MIS）方法不同，Q-MMR 为每个数据点学习一个独立的标量。
• 最小二阶矩原则：由于匹配损失的最小化器通常不唯一，算法选择具有最小经验二阶矩（$\|w^{[n]}_h\|_{[n]}$）的解以控制方差。
• 自顶向下归纳：权重从 $h=0$ 到 $H$ 逐层计算，依赖于上一步的权重。

3. 主要贡献与理论结果

A. 无维度的有限样本保证

主要的理论贡献是定理 1，它提供了 OPE 误差的数据依赖有限样本界。在标准的可实现性假设（$Q^\pi \in \mathcal{F}$）下，以至少 $1-\delta$ 的概率：
$$|\hat{J}(\pi) - J(\pi)| \leq \sum_{h=1}^H \hat{L}_h(\hat{w}^{[n]}_h; \hat{w}^{[n]}_{h-1}) + \sum_{h=0}^H \epsilon^{\text{stat}}_h$$
其中：

• $\hat{L}_h$ 是算法实现的经验匹配损失。
• $\epsilon^{\text{stat}}_h \propto \| \hat{w}^{[n]}_h \|_{[n]} \sqrt{\frac{\log(1/\delta)}{n}}$。

意义：

• 无维度：该界在主导项中不显式依赖于 $\mathcal{F}$ 的统计复杂度（例如，没有 $\log |\mathcal{F}|$ 项）。这是通过避免对函数类进行联合界（union bounds），转而依赖针对实现权重的集中性论证来实现的。
• 所见即所得（WYSIWYG）：该界可直接从数据计算得出，因为它依赖于观察到的匹配损失和所学权重的二阶矩。
• 更弱的假设：该保证仅在可实现性下成立，无需通常 GFA 所需的更强贝尔曼完备性假设。

B. 与现有方法的联系

本文确立了 Q-MMR 统一并恢复了特殊情况下的已知结果：

• 线性和表格设定：当特化为线性函数类（具有可逆样本协方差）或表格设定时，Q-MMR 分别与线性 FQE和表格 FQE（或基于模型的确定性等价）一致。
• 恢复细粒度界：在这些特殊情况下，Q-MMR 分析恢复了先前线性/表格文献中发现的无维度、$O(1/\sqrt{n})$ 速率（例如 Duan 等人，2020；Yin 和 Wang，2021），弥合了通用分析与线性分析之间的差距。
• 蒙特卡洛与重要性采样：在在线策略设定中，将权重设为 1 可恢复蒙特卡洛估计器。通过特定修改，它还可以恢复逐步重要性采样。

C. 对覆盖率的见解

本文提供了对离线 RL 中覆盖率更深刻的理论理解：

• 权重幅度作为覆盖率：项 $\|w^{[n]}_h\|_{[n]}$（及其总体对应项 $\|w^\star_h\|_{2, d_D}$）充当经验覆盖率参数。
• 覆盖率的本质：通过进一步分析（第 4 节），作者表明所需的“覆盖率”不仅仅是目标策略特征占用 $E_{d^\pi}[\phi]$ 的覆盖率，而是由特定线性动力系统定义的向量（类似于线性分析中的 $\psi_h$）的覆盖率。
• 贝尔曼完备性：在贝尔曼完备性下，总体权重 $w^\star_h$ 完美恢复目标分布 $d^\pi_h$，且控制权重爆炸的稳定性项被 1 界定。若缺乏完备性，稳定性取决于投影转移算子的算子范数，如果系统不稳定，可能导致权重呈指数级增长。

4. 意义与主张

本文声称提供了一个统一的理论框架，解决了 OPE 中通用函数近似与线性/表格分析之间的张力。

• 统一性：它证明了在线性/表格设定中观察到的“无维度”特性并非线性特性的产物，而是在可实现性条件下，只要使用带有非参数权重的矩匹配方法，即可在通用设定中实现。
• 分析的新颖性：该分析被描述为“极其简单”，避免了对函数类进行复杂的联合界。它利用了贝尔曼方程的伸缩性质以及矩匹配目标的特定结构。
• 实际意义：数据依赖的界提供了一种内置的不确定性量化机制，因为误差界可从数据集中计算得出，而无需知道函数类的真实复杂度。

作者指出了局限性，包括需要 i.i.d. 轨迹数据（这在自适应收集时会失效），以及权重优化的贪婪局部性质（未明确考虑下游影响，尽管这是为了避免其他 MIS 方法中发现的双重采样问题而做出的权衡）。

总之，Q-MMR 提供了一种理论严谨、无维度的 OPE 方法，它将线性方法的有利特性推广到通用函数类，同时仅依赖可实现性。