在预算与覆盖率双重约束下，找到最优政策分配方案。
Optimal Policy Learning under Budget and Coverage Constraints
- 用影子价格构建线性阈值规则，解决组合优化问题。
- 线性规划松弛的整数差距为常数，近似等价于最优离散分配。
- 贪心-拉格朗日法在小样本中表现接近最优，适合实际应用。
我们研究在预算和最低覆盖率双重约束下的最优政策学习问题。证明该问题具有类似背包的结构，最优策略可由同时包含预算与覆盖率影子价格的仿射阈值规则刻画。建立线性规划松弛的整数间隙为O(1)，表明其渐近等价于最优离散分配。基于此结果，分析两种可实施方法：贪心-拉格朗日（GLC）与排序-切割（RC）算法。结果显示，GLC能紧密逼近最优解，在有限样本中表现接近最优；而RC仅在覆盖率约束宽松或成本同质时近似最优，当成本异质性与紧约束交互时才会出现误分配。蒙特卡洛模拟验证了这些结论。
原文摘要 · Abstract (English)
We study optimal policy learning under combined budget and minimum coverage constraints. We show that the problem admits a knapsack-type structure and that the optimal policy can be characterized by an affine threshold rule involving both budget and coverage shadow prices. We establish that the linear programming relaxation of the combinatorial solution has an O(1) integrality gap, implying asymptotic equivalence with the optimal discrete allocation. Building on this result, we analyze two implementable approaches: a Greedy-Lagrangian (GLC) and a rank-and-cut (RC) algorithm. We show that the GLC closely approximates the optimal solution and achieves near-optimal performance in finite samples. By contrast, RC is approximately optimal whenever the coverage constraint is slack or costs are homogeneous, while misallocation arises only when cost heterogeneity interacts with a binding coverage constraint. Monte Carlo evidence supports these findings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。