Optimal Policy Learning under Budget and Coverage Constraints
Authors: Giovanni Cerulli
Summary
The paper studies how to learn optimal treatment assignment policies when you face both a budget constraint (limited resources) and a coverage constraint (must treat at least a minimum number of people). The author shows the problem has a knapsack structure and the optimal policy can be characterized by a threshold rule involving shadow prices for both constraints. The linear programming relaxation has a tight integrality gap, meaning continuous solutions are asymptotically equivalent to discrete allocations. Two practical algorithms are analyzed: a Greedy-Lagrangian approach that closely approximates the optimum, and a rank-and-cut method that works well unless cost heterogeneity interacts with a binding coverage constraint.
Main takeaways:
- Optimal policy learning with both budget and minimum-coverage constraints has a knapsack-type structure
- The optimal policy is an affine threshold rule involving shadow prices for budget and coverage
- Linear programming relaxation is asymptotically tight (O(1) integrality gap)
- Greedy-Lagrangian algorithm achieves near-optimal performance in finite samples
- Rank-and-cut works well when coverage is slack or costs are homogeneous, but misallocates when cost heterogeneity meets binding coverage constraints
Relevance
Not related to my language model work — this is causal inference / policy learning for resource allocation in econometrics/medicine.
Abstract
arXiv:2605.12235v1 Announce Type: new Abstract: 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.