Resumen Técnico: Aprendizaje de Políticas Óptimas bajo Restricciones de Presupuesto y Cobertura

1. Planteamiento del Problema

El artículo aborda el problema del aprendizaje de políticas óptimas en contextos donde un tomador de decisiones debe asignar un recurso limitado (tratamiento) a una población de $N$ unidades para maximizar el bienestar total (ganancias esperadas). La asignación está sujeta a dos restricciones simultáneas:

1. Restricción de Presupuesto: El costo total del tratamiento no puede exceder un presupuesto fijo $B$ (o un presupuesto per cápita $C$).
2. Restricción de Cobertura Mínima: Una fracción mínima $\rho$ de la población debe ser tratada.

Este problema surge en contextos como la formación para el empleo público, intervenciones médicas o beneficios sociales, donde la eficiencia (maximizar ganancias) debe equilibrarse con la equidad o los requisitos políticos (garantizar una cobertura amplia). El desafío central es que la solución óptima requiere seleccionar un subconjunto de unidades de un conjunto exponencialmente grande de alternativas ($2^N$), formando un problema de optimización combinatoria que es NP-duro.

2. Metodología y Marco Teórico

2.1 Caracterización Primal-Dual

El autor formula el problema dentro de un marco de resultados potenciales. Sea $\tau(x)$ el efecto promedio del tratamiento condicional (CATE) y $c(x)$ el costo de tratar a un individuo con covariables $x$. El objetivo es maximizar $E[\pi(X)\tau(X)]$ sujeto a $E[\pi(X)c(X)] \leq C$ y $E[\pi(X)] \geq \rho$.

Utilizando la dualidad lagrangiana, el artículo establece que la política óptima $\pi^*$ toma la forma de una regla de umbral afín:
$$\pi^*(x) = \mathbb{1}\{ \tau(x) - \lambda^* c(x) + \nu^* \geq 0 \}$$
donde:

• $\lambda^*$ es el precio sombra de la restricción de presupuesto.
• $\nu^*$ es el precio sombra de la restricción de cobertura.
• La regla trata a un individuo si su beneficio, ajustado por el precio sombra de la cobertura, supera el costo escalado por el precio sombra del presupuesto.

Esta estructura difiere de los problemas estándar con restricción de presupuesto (que generan una regla de ratio simple $\tau(x)/c(x) \geq \lambda^*$) porque la restricción de cobertura introduce un desplazamiento aditivo ($\nu^*$), creando una frontera de decisión heterogénea.

2.2 Equivalencia con la Mochila y Relajación de Programación Lineal

Se demuestra que la contraparte empírica del problema es equivalente a un problema de mochila 0-1 con una restricción de cardinalidad adicional.

• Forma Combinatoria: Seleccionar un vector binario $d \in \{0,1\}^n$ para maximizar $\sum \hat{\tau}_i d_i$ sujeto a $\sum c_i d_i \leq nC$ y $\sum d_i \geq n\rho$.
• Relajación de Programación Lineal (LP): La restricción binaria se relaja a $z_i \in [0,1]$.

Un resultado teórico crítico es el análisis del hueco de integralidad (la diferencia entre el valor óptimo de LP y el valor óptimo 0-1). El artículo demuestra que:

1. Cualquier solución de punto extremo de la relajación LP tiene a lo sumo dos componentes fraccionarias.
2. En consecuencia, el hueco de integralidad absoluto está acotado por una constante $O(1)$ (específicamente $2V_{max}$).
3. En términos per cápita, el hueco desaparece asintóticamente como $O(1/n)$. Esto implica que la relajación LP es asintóticamente equivalente a la solución óptima discreta.

2.3 Algoritmos Implementables

Basándose en la relajación LP y la estructura de umbral afín, se proponen dos algoritmos:

1. Greedy–Lagrangian con Cobertura (GLC):

   • Mecanismo: Una búsqueda primal-dual sobre el precio sombra del presupuesto $\lambda$. Para un $\lambda$ fijo, las unidades se puntúan mediante $a_i(\lambda) = \hat{\tau}_i - \lambda c_i$.
   • Procedimiento: El algoritmo hace cumplir la restricción de cobertura forzando a las $K_n$ unidades superiores (mínimo requerido) por puntuación al conjunto de tratamiento, y luego añade greedy las unidades restantes con puntuaciones positivas hasta agotar el presupuesto. El multiplicador $\lambda$ se ajusta mediante bisección para satisfacer la restricción de presupuesto.
   • Complejidad: $O(n \log n \cdot \log(1/\varepsilon))$.

2. Rank-and-Cut (RC):

   • Mecanismo: Una regla heurística no iterativa que clasifica las unidades únicamente por el ratio de costo-efectividad $s_i = \hat{\tau}_i / c_i$.
   • Procedimiento: Las unidades se ordenan por $s_i$ en orden descendente. El algoritmo selecciona el prefijo factible más grande que satisface tanto la restricción de presupuesto como la de cobertura.
   • Complejidad: $O(n \log n)$.

3. Resultados Clave

3.1 Optimalidad Asintótica

El artículo establece que el algoritmo GLC es asintóticamente óptimo. Dado que la relajación LP tiene un hueco de integralidad per cápita que desaparece, cualquier regla greedy factible que aproxime el óptimo de LP (lo cual hace GLC) también es asintóticamente óptima para el problema combinatorio original.

3.2 Rendimiento de Rank-and-Cut (RC)

El artículo proporciona una caracterización precisa de cuándo la regla RC más simple es aproximadamente óptima. La pérdida de bienestar de RC relativa a la política óptima está impulsada por la discrepancia entre el umbral constante utilizado por RC y el umbral afín heterogéneo de la política óptima.

• Condición para Equivalencia: RC es aproximadamente óptima si:
  1. Los costos son homogéneos ($c(x) \approx c_0$), O
  2. La restricción de cobertura es holgada ($\nu^* \approx 0$).
• Condición para Mala Asignación: Una mala asignación significativa ocurre solo cuando la heterogeneidad de costos es sustancial Y la restricción de cobertura es vinculante ($\nu^* > 0$). En este régimen específico, la frontera afín de la política óptima no puede replicarse mediante una clasificación simple basada en ratios, lo que lleva al tratamiento de unidades con bajo ratio (para cumplir la cobertura) y a la exclusión de unidades con alto ratio (debido al presupuesto).

3.3 Evidencia de Monte Carlo

Dos estudios de simulación respaldan los hallazgos teóricos:

1. GLC vs. LP: A medida que aumenta el tamaño de la muestra $n$, el arrepentimiento per cápita de GLC relativo a la solución óptima exacta (MILP) disminuye rápidamente, estabilizándose en niveles bajos. El hueco de integralidad de LP también desaparece rápidamente, confirmando la convergencia $O(1/n)$.
2. RC vs. LP: Las simulaciones en cuatro regímenes (variando la heterogeneidad de costos y la rigidez de la cobertura) confirman que la mala asignación entre RC y la política óptima es insignificante en todos los casos excepto cuando los costos son heterogéneos y la cobertura es vinculante. En ese escenario específico de "peor caso", el área de mala asignación es significativa (~15%), validando el efecto de interacción teórico.

4. Contribuciones y Significado

El artículo realiza tres contribuciones principales:

1. Representación Estructural: Proporciona una caracterización estructural del aprendizaje de políticas con restricciones como un problema tipo mochila con una regla de umbral afín que involucra dos precios sombra, modelando explícitamente la interacción entre las restricciones de presupuesto y cobertura.
2. Precisión Asintótica: Establece que la relajación LP de este problema combinatorio tiene un hueco de integralidad de $O(1)$, demostrando la equivalencia asintótica entre las soluciones relajadas y discretas en términos per cápita. Esto justifica el uso de reglas más simples y escalables en aplicaciones a gran escala.
3. Implementación y Límites: Propone y analiza dos algoritmos escalables (GLC y RC). Crucialmente, identifica las condiciones estructurales precisas bajo las cuales falla la regla RC simple y no iterativa. El artículo cierra la brecha entre el aprendizaje de políticas estadístico y la optimización combinatoria, ofreciendo un marco que es tanto teóricamente fundamentado como computacionalmente escalable.

El significado del trabajo radica en su capacidad para ir más allá de la caracterización teórica de las políticas óptimas para proporcionar soluciones implementables y escalables con garantías de rendimiento. Aclara que, aunque la clasificación simple por costo-efectividad suele ser suficiente, los responsables políticos deben ser conscientes de las condiciones estructurales específicas (costos heterogéneos + cobertura vinculante) donde tales heurísticas pueden conducir a pérdidas significativas de bienestar.