Optimal Policy Learning under Budget and Coverage Constraints
For policymakers allocating resources under both budget and coverage constraints, this work provides a theoretically grounded and practically implementable solution.
The paper studies optimal policy learning under budget and minimum coverage constraints, showing the problem has a knapsack-type structure and that the optimal policy can be characterized by an affine threshold rule. The proposed Greedy-Lagrangian algorithm achieves near-optimal performance in finite samples.
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.