Budgeted Multi-Source Counterfactual Annotation for Off-Policy Evaluation¶

会议: NeurIPS 2026
arXiv: 2610.10974
OpenReview: https://openreview.net/forum?id=446GKdY1L2
领域: 因果推理
关键词: 离线策略评估、反事实标注、多源预算分配、主化最小化、上下文老虎机

一句话总结¶

针对上下文老虎机离线策略评估中历史行为策略覆盖受限的痛点，提出一种在成本与容量约束下的多源反事实标注预算分配框架，从理论上推导了首个标注门槛与四类局部价值区间，并通过主化最小化算法单调优化估计量方差，使 OPE 估计均方误差降低达 20.68%。

研究背景与动机¶

离线策略评估（Off-Policy Evaluation, OPE）旨在利用已由历史行为策略记录的静态交互日志，评估一个未经部署的新目标策略的预期表现。该技术在个性化医疗诊疗、智能教育辅导及推荐系统等领域尤为关键，因为在这些高风险或高成本环境中，直接上线未经验证的新策略可能带来不可挽回的健康风险或高昂试错代价。然而，在上下文老虎机设定下，历史日志天然存在严重的反事实缺失——即系统仅记录了实际采纳动作的即时回报，对未选替代动作一无所知。当新策略倾向于选择历史日志中采样概率极低甚至未覆盖的动作时，传统重要性采样（IS）会导致权重剧烈震荡引发高方差，而直接模型拟合法则会遭受分布外外推误差，导致策略评估的均方误差急剧上升。

反事实标注为打破这一覆盖瓶颈提供了切实途径。例如，在临床医疗中可由专家医生推断患者采纳替代用药后的预期转归，在智能教学中可借助大语言模型（LLM）模拟学生在替代习题下的作答耗时。近年提出的双重稳健估计量（如 DM+-IS）已能通过仅将标注注入奖励模型拟合阶段，在理论上确保最终策略评估严格无偏。然而，现实中的反事实标注源在成本与质量上存在极强异质性：人类医学专家准确率高但单次咨询费用昂贵；LLM 可以大规模廉价调用，却往往在特定上下文-动作对上存在不可忽视的系统性偏置与额外随机扰动。面对有限的项目预算与样本容量，研究者长期面临一个核心决策困境：究竟应该向谁采购标注、采购多少，以及优先补全哪些上下文-动作对？

这一资源分配决策的核心症结在于，反事实标注的统计价值并非静态属性，而是与目标策略关注度、行为策略覆盖匮乏度、数据已有事实样本量以及各源偏置的相互正负抵消效应紧密交织；更关键的是，同一上下文下不同动作的标注偏置通过双重稳健模型的方差项产生非线性交叉耦合，使得全局离散分配问题兼具非凸性与非次模性。本文的切入角度是将多源反事实数据采购严谨形式化为方差最小化的受约束整数规划问题。核心 idea：将多源反事实标注采购建模为最小化 OPE 方差的整数规划问题，严谨推导首个标注准入阈值与四类局部价值区间，并提出基于凹项仿射主化与分层动态规划的主化最小化（MM）算法，实现单调递减的高效预算分配。

方法详解¶

整体框架¶

本文针对有限上下文空间 $\mathcal{S}$ 与动作空间 $\mathcal{A}$ 的上下文老虎机 OPE 任务，构建了一个端到端的多源反事实标注预算分配优化架构。算法的输入包括历史拟合数据集 $\mathcal{D}_{\text{fit}}$（包含各上下文-动作对的事实观测频数 $n_f(s,a)$、回报真实均值 $\mu_r(s,a)$ 与方差 $\sigma_r^2(s,a)$）、目标策略 $\pi_e$、行为策略 $\pi_b$、各标注源 $k \in \mathcal{K}$ 的单价 $c_k$ 及其先导估计的偏置 $\varepsilon_{g_k}(s,a)$ 与过量方差 $\Delta_{g_k}(s,a)$，以及总预算 $\kappa$。

系统执行流程包含三个核心阶段：首先，通过对 DM+-IS 估计量方差的严格解耦，推导出仅依赖于分配决策 $\mathbf{n}$ 的目标泛函 $J(\mathbf{n})$，并分析单源局部边际回报所遵循的四个价值区间；其次，在全局多源分配中，针对导致跨动作非凸耦合的负偏置平方和项 $-J_2(\mathbf{n})$，构造局部紧致的切线仿射上界，将原非分问题转化为完全可分的主化代理目标；最后，利用拉格朗日乘子松弛全局预算约束，在底层运用成对交换局部搜索优化多源混配比例，在顶层通过动态规划沿上下文容量聚合各动作分配量，并借助二分搜索确保在预算行内单调收敛。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入：日志频数与方差、先导源档案<br/>目标策略与行为策略、总预算与容量"] --> B["估计量方差解耦与目标构建<br/>分离分配无关常数，得到目标泛函 J(n)"]
    B --> C["局部区间判定与首个标注门槛<br/>划分四类渐近行为，识别偏置抵消机会"]
    C --> D["凹项切线主化松弛<br/>构造紧致仿射上界，实现跨动作完全可分"]
    D --> E["分层求解与拉格朗日乘子二分<br/>成对交换局部搜索源配比 + 动态规划聚合动作"]
    E --> F["输出：单调优化整数分配方案 n*<br/>注入奖励模型进行无偏 DM+-IS 策略评估"]

关键设计¶

1. 估计量方差精准解耦与分配敏感目标函数 离线评估的核心难点在于标注数据的引入如何定量改变最终评估器的精度。作者在独立样本划分协议下扩展了双重稳健 DM+-IS 估计量：将收集到的反事实标注仅用于增强回归奖励模型 $\hat{r}^+(s,a)$，而在重要性采样项中保持事实观测。理论分析证明，即使反事实标注存在系统性偏置，该估计量关于目标策略真实价值仍保持严格无偏。其均方误差可严格分解为与分配无关的常数项 $C_0$ 和分配相关目标项 $J(\mathbf{n})$： $$\operatorname{MSE}(\mathbf{n}) = C_0 + \frac{J(\mathbf{n})}{N}$$ 其中目标泛函 $J(\mathbf{n})$ 包含三个具有清晰物理意义的组件： $$J(\mathbf{n}) = \sum_{s,a} \alpha_1(s,a) B(s,a;\mathbf{n})^2 - \sum_s d_0(s) \left(\sum_a \pi_e(a|s) B(s,a;\mathbf{n})\right)^2 + \sum_{s,a} \alpha_3(s,a) W(s,a;\mathbf{n})$$ 权重项定义为 $\alpha_1(s,a) = d_0(s) \pi_e(a|s)^2 / \pi_b(a|s)$，$\alpha_3(s,a) = (1 - \pi_b(a|s)) \alpha_1(s,a)$，而 $B(s,a;\mathbf{n})$ 与 $W(s,a;\mathbf{n})$ 分别代表引入反事实标注后奖励模型的有效偏差与有效方差。式中的第二项负号表征了同一上下文中不同动作的偏差聚合项，第三项则反映了方差缩减程度。这一分解明确表明，标注的价值取决于目标策略关注度、行为策略稀缺度和已有事实覆盖度的交互作用，使优化分配具有坚实的统计基础。

2. 首个标注准入阈值与四类标注价值局部区间 实践中关于多源标注常存在误区，要么盲目认为额外数据必然降低方差，要么无法判断有偏标注的采纳边界。针对单一上下文-动作对，作者推导了采纳第 1 个标注时不恶化局部目标（$\delta\phi(0) \le 0$）的充要条件（首个标注阈值）： $$\varepsilon_g^2(s,a) \le (1 - \pi_b(a|s)) \left( \frac{n_f(s,a) + 1}{n_f(s,a)} \sigma_r^2(s,a) - \Delta_g(s,a) \right)$$ 该公式清晰表明：当事实观测 $n_f$ 极多时，$(n_f+1)/n_f \to 1$，方差缩减空间极小，允许的偏置容忍度迅速收紧；而若过量方差 $\Delta_g \ge (n_f+1)\sigma_r^2/n_f$，任何带偏置的标注都将导致方差不降反增。进一步，通过分析连续松弛导数的符号变化，论文严格界定了四个标注价值区间： - 区间 I（本地有害）：高偏置高方差，目标函数单调递增，局部最优决策为不采购（$n=0$）； - 区间 II（有限收益）：低方差中偏置，目标函数先降后升，存在唯一连续极值点 $n^*$，最佳决策是采购有限量并在此止步； - 区间 III（单调收益）：极低偏置低方差，目标函数单调递减，每新增一个标注均能降低方差，最佳决策是在预算或容量允许下尽可能多采； - 区间 IV（需大批量突破）：高方差中偏置，目标函数先升后降，必须一次性采购突破临界规模才可能实现净收益，否则小规模尝试反而有害。

3. 凹项切线主化与分层动态规划算法（MM-DP） 跨动作偏差项 $-J_2(\mathbf{n}) = -\sum_s d_0(s) \mathcal{B}_s(\mathbf{n})^2$ 导致目标函数关于决策变量非可分、非凸且非次模，无法直接应用常规整数规划工具。作者提出基于主化最小化（MM）的解耦策略：利用负平方函数的凸对偶切线，在当前迭代点 $\mathbf{n}^{(t)}$ 处构建全局紧致仿射上界： $$\tilde{J}(\mathbf{n}; \mathbf{n}^{(t)}) = J_1(\mathbf{n}) + J_3(\mathbf{n}) - 2 \sum_{s \in \mathcal{S}} d_0(s) \mathcal{B}_s(\mathbf{n}^{(t)}) \mathcal{B}_s(\mathbf{n})$$ 该代理函数在当前点处精确切合原函数（即 $\tilde{J}(\mathbf{n}^{(t)}; \mathbf{n}^{(t)}) = J(\mathbf{n}^{(t)})$），且其第三项完全分解为各动作的独立线性项，使代理目标关于所有上下文-动作对完全可分。随后，算法引入乘子 $\lambda$ 松弛全局预算，将问题拆解为两层高效子例程：底层针对特定 $(s,a)$，利用成对交换局部搜索（Pairwise-Exchange Local Search）快速寻找在固定总标注量 $m$ 下使惩罚代理成本最小的多源混配向量；顶层利用动态规划在每个上下文内部，在总样本容量约束 $\sum_a m_{s,a} \le N_s$ 下精确求解各动作的分配量；外层通过二分法搜索最优乘子 $\lambda$，并在每轮跌代保留历史最优可行解，从数学上严格保证原目标函数单调递减（$J(\mathbf{n}^{(t+1)}) \le J(\mathbf{n}^{(t)})$）。

理论分析与设计权衡¶

在实际落地时，标注源的偏置 $\varepsilon_{g_k}$ 与过量方差 $\Delta_{g_k}$ 通常不可直接获取，需依赖有限先导样本（Pilot）进行估计。作者证明了基于估计档案优化的稳健性边界（Theorem 2）： $$\operatorname{MSE}(\widehat{\mathbf{n}}) - \operatorname{MSE}(\mathbf{n}^*) \le \frac{2 A_1 \delta_\varepsilon (2 \beta_{\max} + \delta_\varepsilon) + 2 A_2 \delta_\Delta + \xi_{\text{alg}}}{N}$$ 其中 $\delta_\varepsilon$ 与 $\delta_\Delta$ 分别为偏置与过量方差的最大估计误差，$A_1, A_2$ 为问题固有灵敏度常数，$\xi_{\text{alg}}$ 为算法优化间隙。该定理表明，先导估计误差对最终 OPE 均方误差的影响以一阶线性受控，当先导样本规模扩大使得估计误差趋向于零时，性能损失严格收敛至算法优化间隙 $\xi_{\text{alg}}/N$。因此，在实践中仅需分配极小比例的预算（如每对采集 20 次先导样本）即可建立充分可靠的质量剖面。

实验关键数据¶

主实验¶

实验在三套代表性场景中展开评估：基于 616 万条真实学生答题记录构建的 ASSISTments 教育老虎机（100 个上下文，10 个动作，采用 Gemini-2.5-Flash、GPT-4o-mini、Claude-Haiku-4.5 作为标注源）、原始合成临床老虎机（100 个上下文，5 个动作），以及专门测试局部非凸特性的 I/IV 区间主导合成老虎机。评估指标为估计器的总缩放均方误差 $\mathcal{V}(\mathbf{n}) = N \operatorname{MSE}(\mathbf{n})$。

数据集 / 场景	无标注基线 (No ann.)	成本感知贪心 (Greedy-cost)	最大增益贪心 (Greedy-gain)	本文 MM (零初始化)	本文 MM (贪心初始化)	相对无标注降幅
ASSISTments 教育真实 LLM 场景	88.608	79.198	79.707	79.062	79.062	-10.77%
Original Synthetic 临床场景	84.234	69.275	67.078	66.901	66.808	-20.68%
I/IV-focused Synthetic 场景	84.234	72.644	71.718	70.663	70.720	-16.11%

消融实验¶

为定量评估 MM 算法与全局最优解的逼近程度，作者在 30 个小规模可解实例（5 上下文，3 动作，25 样本）上使用 Gurobi 求解多重选择背包混合整数规划获取认证全局最优解，对比各算法的相对 MSE 间隙。

算法配置	平均相对间隙 (Mean Gap)	标准差 (Std Gap)	中位数间隙 (Median Gap)	最大间隙 (Max Gap)	性能说明
Greedy (cost-aware)	3.67%	3.12%	3.37%	17.38%	容易因局部性价比误导产生严重次优
Greedy (max-gain)	0.30%	0.30%	0.23%	0.98%	忽略成本协同，无法克服非次模性
MM (零初始化)	0.31%	0.27%	0.26%	1.08%	无需贪心引导即能稳定收敛至高质量解
MM (贪心初始化)	0.05%	0.07%	0.02%	0.26%	极度贴近认证全局最优解

关键发现¶

非凸区间的跨越能力：在 I/IV 区间主导的场景中，单个标注会暂时增加方差（区间 IV 的先增后降特性），传统单步贪心策略因无法获得即时正向收益而过早陷入局部停滞；MM 算法通过切线代理和全局动态规划能够有效进行批量跨越，取得了比最大增益贪心法更显著的方差降幅（70.663 vs 71.718）。
极小全局优化间隙：在小规模认证基准上，贪心初始化的 MM 算法平均距离理论最优解仅有 0.05% 的误差，且在全尺寸合成与 ASSISTments 数据集上，距离 Gurobi 理论松弛下界分别仅相差 0.2807% 和 0.0050%，证实了该多项式时间算法具备准全局最优性。
有限先导样本的稳健性：在仅使用 20 次先导抽样估计各源偏置与方差的情况下，结合 50 次独立评估运行，贪心初始化的 MM 仍能在真实评估数据上实现 19.13%（Synthetic）和 8.47%（ASSISTments）的实际经验 MSE 下降；且在 30 次 Bootstrap 重抽样下方差波动不足 0.0038 个百分点，充分验证了理论误差界在现实场景中的可靠性。

亮点与洞察¶

理论框架深刻完备：将统计因果推断中的无偏 OPE 估计器方差分解与组合优化严密结合，从数学上澄清了“有偏廉价数据能否提升评估精度”的本质取决于偏置与方差缩减的代数竞合。
四个标注区间的直观刻画：首创性地提出了首个标注准入阈值与四个价值区间，为工业界在选择高价专家还是低价 LLM 标注时提供了直接可执行的定性与定量筛查准则。
凹项主化的巧妙解耦：通过一阶仿射上界完全消除了跨动作偏差的复杂二次耦合，使得带有容量限制的组合分配问题能够通过经典的二分乘子法与动态规划在多项式时间内精确求解。

局限与展望¶

模型假设局限于单步老虎机：当前理论与算法针对有限状态与动作空间的上下文老虎机设计，尚未直接推广至长时序决策的马尔可夫决策过程（MDP）。在序贯决策中状态转移误差的复合传播将大幅增加方差解耦的难度。
依赖预先固定的先导档案：当前框架假设各源的质量剖面在采购前通过独立的 Pilot 阶段估计完成，属于离线静态分配。未来可探索与主动学习相结合的在线序贯采集机制，在分配过程中自适应更新对标注源的置信度。
教育与医疗实验仍含半合成成分：虽然采用了真实的 Gemini/GPT/Claude 大模型标注输出，但教育与临床环境的回报生成机制仍基于 IRT 建模与合成动力学，完全真实临床闭环中的人类标注实验仍有待进一步验证。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次从统计最优性视角系统解决多源有偏反事实标注的预算分配难题，理论区间划分极为深刻。
实验充分度: ⭐⭐⭐⭐⭐ 涵盖真实 LLM 交互数据集、多种合成动力学、小规模 Gurobi 认证全局最优及有限先导稳健性实验。
写作质量: ⭐⭐⭐⭐⭐ 数学推导严谨自洽，方差分解与算法设计环环相扣，逻辑脉络极为清晰。
价值: ⭐⭐⭐⭐⭐ 为大模型辅助决策、医疗与在线教育系统中的低成本策略离线验证提供了高实用价值的理论指导与算法工具。