技术摘要：预算与覆盖率约束下的最优策略学习

1. 问题陈述

本文探讨了在决策者必须向 $N$ 个单元的群体分配有限资源（干预措施）以最大化总福利（预期收益）的情境下的最优策略学习问题。该分配需同时满足两个约束：

1. 预算约束：干预措施的总成本不得超过固定预算 $B$（或人均预算 $C$）。
2. 最低覆盖率约束：必须对至少 $\rho$ 比例的人口进行干预。

此类问题出现在公共就业培训、医疗干预或社会福利等场景中，需要在效率（最大化收益）与公平性或政治要求（确保广泛覆盖）之间取得平衡。核心挑战在于，最优解需要从指数级庞大的替代方案集合（$2^N$）中选择一个子集，这构成了一个 NP 难的组合优化问题。

2. 方法论与理论框架

2.1 原始 - 对偶特征

作者在潜在结果框架内构建了该问题。令 $\tau(x)$ 为条件平均处理效应（CATE），$c(x)$ 为对具有协变量 $x$ 的个体进行干预的成本。目标是在满足 $E[\pi(X)c(X)] \leq C$ 和 $E[\pi(X)] \geq \rho$ 的条件下，最大化 $E[\pi(X)\tau(X)]$。

利用拉格朗日对偶性，本文确立了最优策略 $\pi^*$ 采取仿射阈值规则的形式：
$$\pi^*(x) = \mathbb{1}\{ \tau(x) - \lambda^* c(x) + \nu^* \geq 0 \}$$
其中：

• $\lambda^*$ 是预算约束的影子价格。
• $\nu^*$ 是覆盖率约束的影子价格。
• 该规则在个体的收益（经覆盖率影子价格调整后）超过经预算影子价格缩放的成本时，对其进行干预。

这种结构不同于标准的预算约束问题（后者产生简单的比率规则 $\tau(x)/c(x) \geq \lambda^*$），因为覆盖率约束引入了一个加法偏移量（$\nu^*$），从而形成了一个异质的决策边界。

2.2 背包等价性与线性规划松弛

该问题的实证对应形式被证明等价于带有额外基数约束的0-1 背包问题。

• 组合形式：选择二进制向量 $d \in \{0,1\}^n$ 以最大化 $\sum \hat{\tau}_i d_i$，受限于 $\sum c_i d_i \leq nC$ 且 $\sum d_i \geq n\rho$。
• 线性规划（LP）松弛：将二进制约束松弛为 $z_i \in [0,1]$。

一个关键的理论结果是对积分间隙（LP 最优值与 0-1 最优值之间的差异）的分析。本文证明了：

1. LP 松弛的任何极点解最多具有两个分数分量。
2. 因此，绝对积分间隙被常数 $O(1)$ 界定（具体为 $2V_{max}$）。
3. 在人均意义上，该间隙随 $O(1/n)$ 渐近消失。这意味着 LP 松弛在渐近意义上等价于离散最优解。

2.3 可实施算法

基于 LP 松弛和仿射阈值结构，提出了两种算法：

1. 带覆盖率的贪婪 - 拉格朗日法（GLC）：

   • 机制：对预算影子价格 $\lambda$ 进行原始 - 对偶搜索。对于固定的 $\lambda$，根据 $a_i(\lambda) = \hat{\tau}_i - \lambda c_i$ 对单元进行评分。
   • 过程：算法通过强制将按评分排序的前 $K_n$ 个（最低要求）单元纳入干预集来执行覆盖率约束，然后贪婪地添加剩余的正分单元直到预算耗尽。通过二分法调整乘数 $\lambda$ 以满足预算约束。
   • 复杂度：$O(n \log n \cdot \log(1/\varepsilon))$。

2. 排序 - 截断法（RC）：

   • 机制：一种非迭代的启发式规则，仅根据成本效益比 $s_i = \hat{\tau}_i / c_i$ 对单元进行排序。
   • 过程：按 $s_i$ 降序排列单元。算法选择满足预算和覆盖率约束的最大可行前缀。
   • 复杂度：$O(n \log n)$。

3. 主要结果

3.1 渐近最优性

本文确立了 GLC 算法具有渐近最优性。由于 LP 松弛的人均积分间隙趋于消失，任何逼近 LP 最优解的可行贪婪规则（GLC 即属此类）对于原始组合问题也是渐近最优的。

3.2 排序 - 截断法（RC）的性能

本文精确刻画了更简单的 RC 规则何时近似最优。RC 相对于最优策略的福利损失，主要由 RC 使用的常数阈值与最优策略的异质仿射阈值之间的差异驱动。

• 等价条件：RC 近似最优的条件是：
  1. 成本是同质的（$c(x) \approx c_0$），或者
  2. 覆盖率约束是松弛的（$\nu^* \approx 0$）。
• 错配条件：显著错配仅发生在成本异质性显著且覆盖率约束具有约束力（$\nu^* > 0$）时。在这种特定机制下，最优策略的仿射边界无法通过简单的基于比率的排序来复制，导致对低比率单元进行干预（以满足覆盖率）并排除高比率单元（由于预算限制）。

3.3 蒙特卡洛证据

两项模拟研究支持了理论发现：

1. GLC 与 LP：随着样本量 $n$ 增加，GLC 相对于精确最优解（MILP）的人均遗憾迅速下降，并稳定在较低水平。LP 积分间隙也迅速消失，证实了 $O(1/n)$ 的收敛性。
2. RC 与 LP：跨越四种机制（变化成本异质性和覆盖率紧密度）的模拟证实，除成本异质且覆盖率具有约束力的情况外，RC 与最优策略之间的错配在所有情况下均可忽略不计。在这种特定的“最坏情况”下，错配区域显著（约 15%），验证了理论上的交互效应。

4. 贡献与意义

本文做出了三项主要贡献：

1. 结构表征：它提供了约束策略学习的结构表征，将其建模为带有仿射阈值规则的背包型问题，该规则涉及两个影子价格，明确模拟了预算与覆盖率约束之间的相互作用。
2. 渐近紧致性：它确立了该组合问题的 LP 松弛具有 $O(1)$ 的积分间隙，证明了松弛解与离散解在人均意义上的渐近等价性。这为在大规模应用中使用更简单、可扩展的规则提供了依据。
3. 实施与局限：它提出并分析了两种可扩展算法（GLC 和 RC）。至关重要的是，它确定了简单的非迭代 RC 规则失效的精确结构条件。本文弥合了统计策略学习与组合优化之间的差距，提供了一个既有理论基础又具计算可扩展性的框架。

这项工作的意义在于，它能够超越对最优策略的理论表征，提供具有性能保证的可实施、可扩展的解决方案。它阐明了虽然简单的成本效益排序通常就足够了，但政策制定者必须意识到特定的结构条件（异质成本 + 具有约束力的覆盖率），在这些条件下，此类启发式方法可能导致显著的福利损失。