Optimal Policy Learning under Budget and Coverage Constraints

📄 arXiv: 2605.12235v1 📥 PDF

作者: Giovanni Cerulli

分类: stat.ML, cs.LG

发布日期: 2026-05-12

💡 一句话要点

提出预算与覆盖约束下的最优策略学习方法

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 最优策略学习 预算约束 覆盖约束 贪婪算法 线性规划 组合优化 影子价格 蒙特卡洛模拟

📋 核心要点

  1. 核心问题：现有方法在预算和覆盖约束下的最优策略学习面临挑战，难以有效平衡资源分配与覆盖需求。
  2. 方法要点：本文提出了贪婪拉格朗日和排序与切割两种算法，通过引入影子价格和仿射阈值规则来优化策略。
  3. 实验或效果：实验结果显示，GLC算法在有限样本中接近最优解，而RC算法在特定条件下表现出近似最优性。

📝 摘要（中文）

本文研究了在预算和最低覆盖约束下的最优策略学习问题。我们证明了该问题具有背包类型的结构，且最优策略可以通过涉及预算和覆盖影子价格的仿射阈值规则来表征。我们建立了组合解决方案的线性规划松弛具有O(1)的整合差距，意味着其与最优离散分配在渐近上是等价的。基于此结果，我们分析了两种可实施的方法：贪婪拉格朗日（GLC）和排序与切割（RC）算法。结果表明，GLC在有限样本中能接近最优解，而RC在覆盖约束松弛或成本均匀时近似最优，只有在成本异质性与绑定覆盖约束相互作用时才会出现错误分配。蒙特卡洛证据支持了这些发现。

🔬 方法详解

问题定义：本文旨在解决在预算和覆盖约束下的最优策略学习问题。现有方法在处理资源分配与覆盖需求的平衡时存在不足，难以实现高效的策略优化。

核心思路：论文的核心思路是通过引入预算和覆盖的影子价格，构建仿射阈值规则来表征最优策略。这种设计使得在复杂约束下仍能有效进行策略优化。

技术框架：整体架构包括两个主要算法模块：贪婪拉格朗日（GLC）算法和排序与切割（RC）算法。GLC算法通过贪婪策略逐步优化，而RC算法则通过对覆盖约束的分析进行切割优化。

关键创新：最重要的技术创新点在于将预算和覆盖约束结合起来，形成了一种新的优化框架，并证明了线性规划松弛的O(1)整合差距，这与现有方法在处理组合优化问题时的局限性形成鲜明对比。

关键设计：关键设计包括影子价格的计算、仿射阈值的设定以及在GLC和RC算法中的具体实现细节，如成本异质性对策略优化的影响等。通过这些设计，算法能够在不同条件下实现较好的性能。

🖼️ 关键图片

fig_0
fig_1

📊 实验亮点

实验结果表明，贪婪拉格朗日（GLC）算法在有限样本中能够接近最优解，表现出优越的性能。相比之下，排序与切割（RC）算法在覆盖约束松弛或成本均匀的情况下也能实现近似最优，显示出良好的适应性。整体上，本文的方法在处理预算和覆盖约束的优化问题上具有显著的提升。

🎯 应用场景

该研究的潜在应用领域包括资源分配、广告投放、供应链管理等多个需要在预算和覆盖约束下进行优化的场景。其实际价值在于提供了一种新的优化策略，能够在复杂约束条件下实现高效的资源利用，未来可能对相关行业的决策支持产生深远影响。

📄 摘要（原文）

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.