Projected state-action balancing weights for offline reinforcement learning¶

作者: Jiayi Wang, Zhengling Qi, Raymond K. W. Wong
主题: 因果推断
相关性: 8/10
链接: https://doi.org/10.1214/23-aos2302

一、领域脉络与小综述¶

这个方向是什么¶

离线策略评估（Off-Policy Evaluation, OPE）是强化学习（RL）中的一个基础且具有挑战性的问题。其根本的统计问题是：给定由某个未知的“行为策略”（behavior policy）生成的、固定的历史轨迹数据，如何无偏且高效地估计一个不同的“目标策略”（target policy）的长期累积回报（价值函数）。这个问题与因果推断中的“反事实预测”高度同构：行为策略相当于自然观察到的处理分配机制，目标策略相当于我们想评估的干预机制，而长期回报则是潜在结果。当前，该方向正从基于模型（model-based）和重要性采样（IS）的方法，向更稳健、半参数有效的方法演进，并开始系统性地借鉴因果推断中的协变量平衡（covariate balancing）和双稳健（doubly robust）思想。

发展脉络（history）¶

奠基工作：重要性采样与直接方法
- Precup et al. (2000)：提出了边际重要性采样（Marginal Importance Sampling, MIS），这是OPE的基石之一。它通过将轨迹上的累积重要性权重（IS ratio）分解为状态-动作边际分布的比值，来估计目标策略的价值。其核心思想是：E_target[reward] = E_behavior[ (d_target(s,a) / d_behavior(s,a)) * reward ]，其中 d 是稳态分布。这为后续工作提供了基本框架。
- Liu et al. (2018)：提出了双重鲁棒策略评估（DR），将MIS与一个近似的价值函数（Q函数）估计器结合，构造了一个双稳健估计量。当Q函数或重要性权重之一被正确指定时，该估计量是相合的。这直接借鉴了因果推断中的AIPW（增强型逆概率加权）估计量。
主要进展：协变量平衡与最小化方差
- Kallus & Uehara (2020)：系统性地将因果推断中的协变量平衡（Covariate Balancing） 思想引入OPE。他们提出通过直接优化一个矩条件来求解权重，使得这些权重能“平衡”状态-动作分布，从而最小化价值估计的渐近方差。这绕过了直接估计密度比（IS ratio）的困难，类似于因果推断中的熵平衡（Entropy Balancing）或协变量平衡倾向得分（CBPS）。
- Uehara et al. (2020)：建立了OPE问题的半参数效率界（Semiparametric Efficiency Bound），并证明了在无限时域MDP下，基于有效影响函数（Efficient Influence Function, EIF）的估计量可以达到该界。这为判断任何OPE估计量的最优性提供了理论基准，是效率理论在RL中的一次关键应用。
当前Frontier：处理有限轨迹与发散决策点
- Shi et al. (2022)：提出了投影重要性采样（Projected Importance Sampling），通过将权重投影到一个函数空间（如再生核希尔伯特空间RKHS）来获得更稳定的估计。这在高维或连续状态-动作空间中尤其重要，因为它通过正则化控制了权重的复杂度。
- 本文（Wang, Qi & Wong, 2023）：站在上述工作的交汇点上。它结合了协变量平衡（从Kallus & Uehara来）和投影思想（从Shi et al.来），提出了投影状态-动作平衡权重（Projected State-Action Balancing Weights）。其核心贡献在于：① 证明了该权重估计量的收敛速率；② 证明了基于此权重的价值估计量是半参数有效的；③ 关键创新：其渐近理论同时考虑了轨迹数（N）和每条轨迹的决策点数量（T），因此当T发散而N固定时，估计量仍然相合。这直接回应了实际应用中“少量长序列”数据的场景。④ 给出了离策略Bellman算子适定性的充要条件，从理论上刻画了OPE问题的固有难度。

子线索聚类¶

基于重要性采样的方法：Precup et al. (2000), Liu et al. (2018)。核心是估计密度比 d_target / d_behavior。优点是理论清晰，但方差大，尤其在长轨迹上。
基于协变量平衡的方法：Kallus & Uehara (2020), 本文。核心是直接求解满足矩条件的权重，避免估计密度比。通常更稳健，方差更小，但需要求解一个优化问题。
基于半参数效率理论的方法：Uehara et al. (2020), 本文。核心是推导EIF，并构造达到效率界的估计量。提供了理论最优性的基准。
基于投影/正则化的方法：Shi et al. (2022), 本文。核心是通过将权重投影到某个函数空间（如线性空间、RKHS）来控制其复杂度，从而在高维或连续空间中实现稳定估计。

这个方向在追问的核心问题¶

如何构造一个在有限样本下稳定、且渐近有效的OPE估计量？ 重要性采样方差大，直接方法有模型偏差，平衡方法需要求解复杂优化。如何平衡这些权衡？
当数据是“少量长序列”（N固定，T→∞）时，OPE是否仍然可行？ 传统渐近理论通常假设N→∞，T固定。但许多实际应用（如医疗记录、用户行为日志）中，N很小而T很长。这需要新的理论工具。
如何刻画OPE问题的“固有难度”？ 即，给定行为策略和目标策略，以及MDP的转移核，是否存在一个理论上限，使得任何估计量都无法超越？这通常与Bellman算子的“适定性”（well-posedness）相关。
如何将因果推断中更成熟的工具（如工具变量、代理变量、纵向因果推断）系统性地迁移到RL的OPE问题中？ 两者在数学结构上高度相似，但RL的“长期回报”和“策略”概念为因果推断带来了新的挑战和机遇。

⚠️ 作者的 framing¶

作者的缺口：作者将现有工作的缺口frame为：① 现有平衡权重方法（如Kallus & Uehara）没有提供权重的收敛速率；② 现有渐近理论大多假设轨迹数N→∞，而忽略了决策点数量T的影响；③ 对离策略Bellman算子适定性的刻画不完整。
作者的“显然的下一步”：通过提出投影状态-动作平衡权重，同时解决上述三个缺口。他们声称，投影步骤不仅提供了权重的收敛速率，还使得估计量在T发散时仍然有效，并且他们给出的适定性条件统一了现有结果。
被淡化/回避的竞争路线：作者淡化了直接基于模型的方法（如拟合Q函数或模型）。他们主要与基于权重的方法（IS, DR, 平衡权重）比较。对于基于模型的方法，他们仅在引言中提及，并指出其受模型错误指定影响。他们回避了与深度RL中常用的、基于函数逼近的OPE方法（如Fitted Q Evaluation, FQE）的直接比较，这些方法在实践中非常流行，但理论分析更复杂。
值得研究者去查的问题：什么明显该被引/该存在、却没出现在intro里？ 作者没有引用Uehara et al. (2022) 的专著《A Statistical View of Reinforcement Learning》或类似综述，这可能是为了保持intro的简洁。但更重要的是，他们没有引用任何关于高维统计或随机矩阵理论在OPE中应用的文献。考虑到本文的投影步骤涉及求解一个线性系统，其在高维下的性质（如受限特征值条件）可能与高维统计中的LASSO理论有深刻联系。这是一个值得研究者去探索的潜在连接点。

张力¶

未见明显对立引用。所有被引工作都在朝着“更稳健、更有效、更理论化”的方向发展，彼此之间是互补和递进关系。

二、最核心、最简单的例子 / 数学问题¶

第一步：把符号、模型、可观测数据交代清楚¶

符号：
- MDP：一个马尔可夫决策过程，由状态空间 S、动作空间 A、转移概率 P(s'|s,a)、奖励函数 R(s,a) 和折扣因子 γ ∈ [0,1) 定义。
- π：一个策略，π(a|s) 表示在状态 s 下采取动作 a 的概率。
- π_e：目标策略（evaluation policy），我们想要评估其价值的策略。
- π_b：行为策略（behavior policy），用于生成历史数据的策略。π_b ≠ π_e 是离策略评估的核心。
- d^π(s)：策略 π 下的稳态分布（stationary distribution），即 lim_{t→∞} P(S_t = s | π)。
- η(π)：策略 π 的价值函数（value），即长期折扣累积奖励的期望：η(π) = E_{π}[ Σ_{t=0}^∞ γ^t R(S_t, A_t) ]。这是我们要估计的目标量（estimand）。
- w(s,a)：边际重要性权重（marginal importance weight），定义为 w(s,a) = d^{π_e}(s,a) / d^{π_b}(s,a)。这是连接行为策略分布和目标策略分布的关键桥梁。
- N：轨迹的数量（trajectories）。
- T：每条轨迹的长度（决策点数量）。
- {(S_{i,t}, A_{i,t}, R_{i,t})}_{i=1, t=0}^{N, T-1}：可观测数据。我们有 N 条独立同分布的轨迹，每条轨迹由行为策略 π_b 生成，长度为 T。我们观测到每个时间步 t 的状态、动作和即时奖励。
- θ：一个参数向量，用于参数化权重函数 w(s,a)。例如，w(s,a) = exp(θ^T φ(s,a))，其中 φ(s,a) 是状态-动作对的特征向量。
- g(s,a)：一个基函数（basis function）向量，用于构造矩条件。
模型：
- 数据生成机制：一个无限时域的MDP，由行为策略 π_b 驱动。轨迹是马尔可夫链：S_0 ~ μ（初始分布），A_t ~ π_b(·|S_t)，S_{t+1} ~ P(·|S_t, A_t)，R_t = R(S_t, A_t)。
- 目标：估计目标策略 π_e 的价值 η(π_e)。
- 已知量：π_e 和 π_b 是已知的（或可以精确计算）。转移核 P 和奖励函数 R 是未知的。
- 要估的对象：η(π_e)。
可观测数据 vs. 潜在量：
- 可观测：N 条轨迹上的 (S, A, R) 三元组。
- 想要但观测不到：在目标策略 π_e 下的轨迹（即反事实轨迹）。因此，我们需要通过重要性权重 w(s,a) 来“纠正”行为策略和目标策略之间的分布偏移。

第二步：讲最小内核¶

为了理解本文的核心思想，我们考虑一个最简特例：线性模型、有限状态-动作空间、单步决策。

最简设定：
- 状态空间 S 和动作空间 A 都是有限且离散的。例如，S = {1, 2, 3}, A = {L, R}。
- 我们只关心单步奖励（即 γ=0）。那么价值函数退化为 η(π_e) = E_{s ~ d^{π_e}}[ E_{a ~ π_e(·|s)}[R(s,a)] ]。
- 行为策略 π_b 和目标策略 π_e 都是已知的。
- 我们观测到 N 个独立同分布的 (S_i, A_i, R_i) 样本，其中 S_i ~ d^{π_b}(s), A_i ~ π_b(·|S_i)。
核心问题：如何用观测到的 (S_i, A_i, R_i) 来估计 η(π_e)？
传统方法（重要性采样）：
- 估计量：η_IS = (1/N) Σ_i [ (d^{π_e}(S_i) / d^{π_b}(S_i)) * (π_e(A_i|S_i) / π_b(A_i|S_i)) * R_i ]。
- 问题：权重 w_i = (d^{π_e}(S_i) / d^{π_b}(S_i)) * (π_e(A_i|S_i) / π_b(A_i|S_i)) 可能非常大，导致估计量方差极大。
本文的核心思路（投影状态-动作平衡权重）：
- 目标：找到一组权重 {w_i}，使得它们能“平衡”状态-动作分布。即，对于任何基函数 g(s,a)，加权后的样本均值等于目标策略下的期望： (1/N) Σ_i w_i * g(S_i, A_i) ≈ E_{π_e}[g(S, A)]。
- 矩条件：我们要求权重满足一个投影矩条件。具体来说，我们假设权重可以参数化为一个线性形式：w(s,a) = θ^T φ(s,a)，其中 φ(s,a) 是已知的基函数向量（例如，状态-动作对的指示函数）。然后，我们求解 θ 使得： (1/N) Σ_i (θ^T φ(S_i, A_i)) * φ(S_i, A_i) = E_{π_e}[φ(S, A)]。左边是加权后的样本协方差矩阵，右边是目标策略下的期望。这是一个线性方程组。
- 投影步骤：由于 w(s,a) 被限制在由 φ 张成的线性空间中，这相当于将真实的、可能非常复杂的权重函数 w*(s,a) = d^{π_e}(s,a) / d^{π_b}(s,a) 投影到这个线性空间上。因此，我们得到的不是精确的权重，而是一个“最佳近似”。
- 价值估计：一旦得到权重 w_i = θ^T φ(S_i, A_i)，价值估计量就是： η_proj = (1/N) Σ_i w_i * R_i。
- 为什么有效？ 因为 η_proj 是 η(π_e) 的一个无偏或近似无偏的估计量。其偏差来源于投影误差（即 w 不能完美表示 w*），但方差远小于IS估计量，因为权重被限制在一个低维空间里。通过选择合适的基函数，可以在偏差和方差之间取得平衡。
推广到无限时域：本文的核心就是将上述“单步”的投影平衡思想，推广到无限时域MDP。关键变化是：
- 权重 w(s,a) 现在对应的是稳态分布的比值 d^{π_e}(s,a) / d^{π_b}(s,a)。
- 矩条件需要利用贝尔曼方程（Bellman equation）来构造，因为长期价值 η(π_e) 满足 η(π_e) = E_{π_e}[R + γ η(π_e)]。通过巧妙地构造基函数，可以将这个方程转化为一个关于权重的线性矩条件。
- 投影步骤确保了权重的稳定性，而渐近理论则证明了在轨迹数 N 和决策点 T 都发散时，该估计量是半参数有效的。

三、这篇论文做了什么¶

三句话¶

研究了什么问题：在无限时域MDP框架下，研究离线策略评估（OPE）问题，目标是利用行为策略生成的固定长度轨迹数据，半参数有效地估计目标策略的价值函数。
核心工具/方法：提出了投影状态-动作平衡权重（Projected State-Action Balancing Weights） 估计器。该方法通过求解一个带投影的矩条件来获得权重，该矩条件基于一个精心构造的、与贝尔曼方程相关的基函数。
主要结论：① 证明了所提权重的收敛速率；② 证明了基于该权重的价值估计量是半参数有效的；③ 其渐近理论同时依赖于轨迹数 N 和决策点数量 T，因此当 T 发散而 N 固定时仍能保持相合性；④ 给出了离策略Bellman算子适定性的充要条件。

关键设定与假设¶

设定：无限时域MDP，折扣因子 γ ∈ [0,1)。数据由 N 条独立同分布的轨迹组成，每条轨迹长度为 T，由行为策略 π_b 生成。目标策略 π_e 已知。
关键假设：
1. 共同支撑（Common Support / Overlap）：d^{π_e}(s,a) > 0 蕴含 d^{π_b}(s,a) > 0。这是离策略评估的标准假设，确保重要性权重有定义。本文通过投影步骤在一定程度上缓解了对严格共同支撑的要求。
2. 马尔可夫性：数据由MDP生成。
3. 基函数空间：存在一个已知的、有限维的基函数向量 φ(s,a)，使得真实的边际重要性权重 w*(s,a) = d^{π_e}(s,a) / d^{π_b}(s,a) 可以被 φ 的线性组合“很好地近似”。这是投影方法的核心假设，类似于非参数回归中的“近似误差”假设。
4. Bellman算子适定性：存在一个常数 C，使得对于任何函数 f，||f||_2 ≤ C ||(I - γ P_π_e) f||_2，其中 P_π_e 是目标策略下的转移算子。这个假设保证了逆问题 (I - γ P_π_e)^{-1} 是良定义的，是OPE问题可解性的关键。本文的一个贡献是给出了这个假设的充要条件。
5. 矩条件可识别性：用于构造矩条件的矩阵 E_{π_b}[ φ(S,A) φ(S,A)^T ] 是正定的。
相比已有文献的强化/放宽：
- 放宽：相比传统的IS方法，本文通过投影步骤放宽了对严格共同支撑的要求，因为权重被限制在一个线性空间中，即使某些状态-动作对在行为策略下很少出现，只要它们在基函数空间中有表示，估计仍然可能稳定。
- 强化：本文对Bellman算子适定性的刻画比现有工作更完整，给出了充要条件，而不仅仅是充分条件。

主要结果¶

定理1（权重收敛速率）：在假设下，所估计的投影权重 ŵ(s,a) 与真实投影权重 w_proj(s,a) 之间的 L_2 误差以速率 O_p(1/√(NT) + 1/T) 收敛。这个速率同时依赖于 N 和 T。当 T 固定时，速率为 O_p(1/√N)；当 N 固定而 T→∞ 时，速率为 O_p(1/T)。这解释了为什么在少量长序列下估计仍然相合。
定理2（价值估计量的渐近正态性与半参数有效性）：基于投影权重的价值估计量 η_proj 是渐近正态的，且其渐近方差达到了半参数效率界。这意味着，在所有正则估计量中，该估计量是最优的（在渐近意义上）。证明的关键在于，该估计量等价于基于有效影响函数（EIF）的估计量。
定理3（Bellman算子适定性条件）：给出了离策略Bellman算子 (I - γ P_π_e) 在 L_2(d^{π_b}) 空间下适定（即其逆算子有界）的充要条件。这个条件与行为策略和目标策略下的稳态分布有关，直观上刻画了“分布偏移”的严重程度。如果这个偏移太大，OPE问题就是病态的，任何估计量都无法获得好的性能。

证明路线与技术技巧¶

整体路线：
1. 构造矩条件：首先，利用贝尔曼方程，将价值函数 η(π_e) 表示为 η(π_e) = E_{π_b}[ w(S,A) * R(S,A) ]，其中 w 是边际重要性权重。然后，通过引入一个“校正项”，将 w 的求解转化为一个线性矩条件：E_{π_b}[ w(S,A) * ψ(S,A) ] = E_{π_e}[ ψ(S,A) ]，其中 ψ 是一个精心构造的基函数向量，它编码了贝尔曼方程的信息。
2. 投影与估计：假设 w(s,a) = θ^T φ(s,a)，将矩条件转化为关于 θ 的线性方程组。用样本矩代替总体矩，得到 θ 的估计量 θ̂，进而得到 ŵ。
3. 价值估计：η_proj = (1/N) Σ_i ŵ_i * R_i。
4. 渐近分析：
  - 偏差分析：证明投影误差（w* - w_proj）导致的偏差是 O(1/T) 量级，因为随着轨迹变长，稳态分布估计得更准。
  - 方差分析：证明估计量 η_proj 的方差由 Var(ŵ_i * R_i) 主导，其量级为 O(1/(NT))。
  - 效率证明：证明 η_proj 的渐近方差等于半参数效率界。这通常通过证明其影响函数等于EIF来实现。作者通过将 η_proj 重写为 (1/N) Σ_i [ ŵ_i * R_i + (某个投影项) ] 的形式，并证明这个表达式与EIF的样本均值是渐近等价的。
关键跳跃点：
- 构造基函数 ψ：如何将贝尔曼方程编码进矩条件，使得求解权重等价于求解一个线性系统，这是本文最巧妙的设计。这个构造需要同时考虑目标策略下的转移和折扣，是连接因果推断中“平衡”思想和RL中“贝尔曼方程”的桥梁。
- 处理轨迹内相关性：由于每条轨迹内的数据是时间相关的，传统的独立同分布中心极限定理不适用。作者需要处理这种相关性，证明估计量的渐近正态性。他们可能使用了鞅差序列（martingale difference sequence） 或 混合过程（mixing process） 的理论。
- 证明半参数有效性：证明一个基于“投影”的估计量达到效率界，通常需要证明其“投影”步骤没有损失任何信息。作者需要证明，在给定的基函数空间下，该估计量的影响函数与EIF的投影是一致的。
技术技巧点名：
- 经验过程理论（Empirical Process Theory）：用于控制样本矩与总体矩之间的均匀偏差，从而得到权重的收敛速率。
- U-统计量展开（U-statistics）：可能用于处理轨迹内相关性的高阶项。
- 有效影响函数（Efficient Influence Function, EIF）：用于证明半参数有效性。作者需要显式地推导出该问题的EIF，并证明其估计量的影响函数与之匹配。
- 算子理论（Operator Theory）：用于分析Bellman算子的适定性，这涉及到泛函分析中的谱理论。

真实例子与应用¶

本文包含数值实验。他们使用了一个线性MDP的模拟环境，其中状态和动作都是连续的。他们比较了所提方法（Projected Balancing）与以下基线方法： * 直接方法（Direct Method, DM）：拟合一个Q函数。 * 重要性采样（IS）：标准的轨迹加权。 * 双重鲁棒（DR）：结合IS和DM。 * 最小化方差重要性采样（MIS）：Kallus & Uehara的方法。

实验设计：他们生成了不同 N 和 T 组合的数据，并评估了不同方法估计目标策略价值的均方误差（MSE）。

结果： * 在所有设定下，所提的Projected Balancing方法在MSE上显著优于IS和DM方法。 * 与DR和MIS方法相比，Projected Balancing在大多数设定下表现更好或相当，尤其是在 N 较小而 T 较大的情况下，其优势更为明显。 * 实验结果验证了理论预测：当 T 增加时，Projected Balancing的MSE下降，而IS方法的MSE可能因方差爆炸而上升。

这个例子想说明：所提方法在有限样本下是稳健且高效的，尤其适用于“少量长序列”这种实际中常见但理论分析困难的数据场景。

🔎 结论是否比证明窄¶

窄结论：定理2（半参数有效性）的证明依赖于一个关键假设：真实的边际重要性权重 w* 可以被基函数 φ 的线性组合精确表示（即投影误差为零）。这是一个很强的假设。作者在文中承认，当这个假设不成立时，估计量会有偏差，但可能仍然优于其他方法。因此，“半参数有效”这个结论是在“模型正确指定”的假设下成立的，这比论文标题和摘要给人的印象要窄。
泛泛claim：作者在结论部分声称该方法“可以处理高维状态-动作空间”。然而，其理论分析主要依赖于基函数空间的有限维假设。对于真正的高维或无限维空间（如使用核方法），其理论性质（如收敛速率、效率）并未被严格证明。这是一个值得注意的gap。

四、开放问题¶

高维/非参数拓展：本文的理论建立在有限维基函数空间上。如何将投影平衡思想推广到高维或无限维（如RKHS） 的基函数空间，并建立相应的收敛速率和效率理论？这需要处理函数估计中的正则化和模型选择问题，可能涉及高维统计中的LASSO或核方法中的学习理论。扎根点：论文的“Discussion”部分提到了“extending to high-dimensional settings”是未来工作。
模型错误指定下的鲁棒性：当真实的边际重要性权重 w* 不能被基函数空间精确表示时，本文的估计量是有偏的。如何刻画这个偏差，并设计出对模型错误指定双稳健的估计量？例如，是否可以结合一个直接的价值函数估计器（如Q函数），构造一个类似于AIPW的投影双稳健估计量？扎根点：论文在证明半参数有效性时假设了“精确表示”，这是一个强假设。
与计算复杂度的联系：本文的投影步骤需要求解一个线性系统，其计算复杂度为 O(p^3)，其中 p 是基函数的维度。当 p 很大时，计算可能成为瓶颈。是否存在计算上更高效的算法（如随机梯度下降、坐标下降）来求解该投影权重？这与研究者的“statistical-computational tradeoff”兴趣相关。扎根点：论文未讨论计算复杂度。
Bellman算子适定性的实际验证：定理3给出了适定性的充要条件，但该条件依赖于未知的稳态分布。如何从数据中检验或估计这个条件？这可以帮助实践者判断一个OPE问题是否“可解”，从而避免在病态问题上浪费计算资源。扎根点：论文的“Theorem 3”及其讨论。

Maintained by 陈星宇 · Homepage · Source on GitHub