Technical Summary: Optimal Policy Learning under Budget and Coverage Constraints

1. Problem Statement

The paper addresses the problem of optimal policy learning in settings where a decision-maker must allocate a limited resource (treatment) across a population of $N$ units to maximize total welfare (expected gains). The allocation is subject to two simultaneous constraints:

1. Budget Constraint: The total cost of treatment cannot exceed a fixed budget $B$ (or per-capita budget $C$).
2. Minimum Coverage Constraint: A minimum fraction $\rho$ of the population must be treated.

This problem arises in contexts such as public employment training, medical interventions, or social benefits, where efficiency (maximizing gains) must be balanced against fairness or political requirements (ensuring broad coverage). The core challenge is that the optimal solution requires selecting a subset of units from an exponentially large set of alternatives ($2^N$), forming a combinatorial optimization problem that is NP-hard.

2. Methodology and Theoretical Framework

2.1 Primal-Dual Characterization

The author formulates the problem within a potential outcomes framework. Let $\tau(x)$ be the conditional average treatment effect (CATE) and $c(x)$ be the cost of treating an individual with covariates $x$. The goal is to maximize $E[\pi(X)\tau(X)]$ subject to $E[\pi(X)c(X)] \leq C$ and $E[\pi(X)] \geq \rho$.

Using Lagrangian duality, the paper establishes that the optimal policy $\pi^*$ takes the form of an affine threshold rule:
$$\pi^*(x) = \mathbb{1}\{ \tau(x) - \lambda^* c(x) + \nu^* \geq 0 \}$$
where:

• $\lambda^*$ is the shadow price of the budget constraint.
• $\nu^*$ is the shadow price of the coverage constraint.
• The rule treats an individual if their benefit, adjusted by the coverage shadow price, exceeds the cost scaled by the budget shadow price.

This structure differs from standard budget-constrained problems (which yield a simple ratio rule $\tau(x)/c(x) \geq \lambda^*$) because the coverage constraint introduces an additive shift ($\nu^*$), creating a heterogeneous decision boundary.

2.2 Knapsack Equivalence and LP Relaxation

The empirical counterpart of the problem is shown to be equivalent to a 0-1 knapsack problem with an additional cardinality constraint.

• Combinatorial Form: Select a binary vector $d \in \{0,1\}^n$ to maximize $\sum \hat{\tau}_i d_i$ subject to $\sum c_i d_i \leq nC$ and $\sum d_i \geq n\rho$.
• Linear Programming (LP) Relaxation: The binary constraint is relaxed to $z_i \in [0,1]$.

A critical theoretical result is the analysis of the integrality gap (the difference between the optimal LP value and the optimal 0-1 value). The paper proves that:

1. Any extreme point solution of the LP relaxation has at most two fractional components.
2. Consequently, the absolute integrality gap is bounded by a constant $O(1)$ (specifically $2V_{max}$).
3. In per-capita terms, the gap vanishes asymptotically as $O(1/n)$. This implies that the LP relaxation is asymptotically equivalent to the discrete optimal solution.

2.3 Implementable Algorithms

Based on the LP relaxation and the affine threshold structure, two algorithms are proposed:

1. Greedy–Lagrangian with Coverage (GLC):

   • Mechanism: A primal-dual search over the budget shadow price $\lambda$. For a fixed $\lambda$, units are scored by $a_i(\lambda) = \hat{\tau}_i - \lambda c_i$.
   • Procedure: The algorithm enforces the coverage constraint by forcing the top $K_n$ (minimum required) units by score into the treatment set, then greedily adds remaining units with positive scores until the budget is exhausted. The multiplier $\lambda$ is tuned via bisection to satisfy the budget constraint.
   • Complexity: $O(n \log n \cdot \log(1/\varepsilon))$.

2. Rank-and-Cut (RC):

   • Mechanism: A non-iterative, heuristic rule that ranks units solely by the cost-effectiveness ratio $s_i = \hat{\tau}_i / c_i$.
   • Procedure: Units are sorted by $s_i$ in descending order. The algorithm selects the largest feasible prefix that satisfies both the budget and coverage constraints.
   • Complexity: $O(n \log n)$.

3. Key Results

3.1 Asymptotic Optimality

The paper establishes that the GLC algorithm is asymptotically optimal. Because the LP relaxation has a vanishing per-capita integrality gap, any feasible greedy rule that approximates the LP optimum (which GLC does) is also asymptotically optimal for the original combinatorial problem.

3.2 Performance of Rank-and-Cut (RC)

The paper provides a precise characterization of when the simpler RC rule is approximately optimal. The welfare loss of RC relative to the optimal policy is driven by the discrepancy between the constant threshold used by RC and the heterogeneous affine threshold of the optimal policy.

• Condition for Equivalence: RC is approximately optimal if:
  1. Costs are homogeneous ($c(x) \approx c_0$), OR
  2. The coverage constraint is slack ($\nu^* \approx 0$).
• Condition for Misallocation: Significant misallocation occurs only when cost heterogeneity is substantial AND the coverage constraint is binding ($\nu^* > 0$). In this specific regime, the affine boundary of the optimal policy cannot be replicated by a simple ratio-based ranking, leading to the treatment of low-ratio units (to meet coverage) and the exclusion of high-ratio units (due to budget).

3.3 Monte Carlo Evidence

Two simulation studies support the theoretical findings:

1. GLC vs. LP: As sample size $n$ increases, the per-capita regret of GLC relative to the exact optimal solution (MILP) decreases rapidly, stabilizing at low levels. The LP integrality gap also vanishes quickly, confirming the $O(1/n)$ convergence.
2. RC vs. LP: Simulations across four regimes (varying cost heterogeneity and coverage tightness) confirm that misallocation between RC and the optimal policy is negligible in all cases except when costs are heterogeneous and coverage is binding. In that specific "worst-case" scenario, the misallocation area is significant (~15%), validating the theoretical interaction effect.

4. Contributions and Significance

The paper makes three primary contributions:

1. Structural Representation: It provides a structural characterization of constrained policy learning as a knapsack-type problem with an affine threshold rule involving two shadow prices, explicitly modeling the interaction between budget and coverage constraints.
2. Asymptotic Tightness: It establishes that the LP relaxation of this combinatorial problem has an $O(1)$ integrality gap, proving asymptotic equivalence between the relaxed and discrete solutions in per-capita terms. This justifies the use of simpler, scalable rules in large-scale applications.
3. Implementation and Limits: It proposes and analyzes two scalable algorithms (GLC and RC). Crucially, it identifies the precise structural conditions under which the simple, non-iterative RC rule fails. The paper bridges the gap between statistical policy learning and combinatorial optimization, offering a framework that is both theoretically grounded and computationally scalable.

The significance of the work lies in its ability to move beyond the theoretical characterization of optimal policies to provide implementable, scalable solutions with performance guarantees. It clarifies that while simple cost-effectiveness ranking is often sufficient, policymakers must be aware of the specific structural conditions (heterogeneous costs + binding coverage) where such heuristics may lead to significant welfare losses.