Sintesi Tecnica: Apprendimento della Politica Ottimale sotto Vincoli di Budget e Copertura

1. Enunciato del Problema

Il documento affronta il problema dell'apprendimento della politica ottimale in contesti in cui un decisore deve allocare una risorsa limitata (trattamento) su una popolazione di $N$ unità per massimizzare il benessere totale (guadagni attesi). L'allocazione è soggetta a due vincoli simultanei:

1. Vincolo di Budget: Il costo totale del trattamento non può superare un budget fisso $B$ (o un budget pro capite $C$).
2. Vincolo di Copertura Minima: Una frazione minima $\rho$ della popolazione deve essere trattata.

Questo problema sorge in contesti quali la formazione per l'impiego pubblica, gli interventi medici o i benefici sociali, dove l'efficienza (massimizzazione dei guadagni) deve essere bilanciata con equità o requisiti politici (garantire una copertura ampia). La sfida principale è che la soluzione ottimale richiede la selezione di un sottoinsieme di unità da un insieme esponenzialmente grande di alternative ($2^N$), formando un problema di ottimizzazione combinatoria che è NP-difficile.

2. Metodologia e Quadro Teorico

2.1 Caratterizzazione Primal-Duale

L'autore formula il problema all'interno di un quadro basato sugli esiti potenziali. Sia $\tau(x)$ l'effetto medio del trattamento condizionato (CATE) e $c(x)$ il costo di trattare un individuo con covariate $x$. L'obiettivo è massimizzare $E[\pi(X)\tau(X)]$ soggetto a $E[\pi(X)c(X)] \leq C$ e $E[\pi(X)] \geq \rho$.

Utilizzando la dualità lagrangiana, il documento stabilisce che la politica ottimale $\pi^*$ assume la forma di una regola di soglia affine:
$$\pi^*(x) = \mathbb{1}\{ \tau(x) - \lambda^* c(x) + \nu^* \geq 0 \}$$
dove:

• $\lambda^*$ è il prezzo ombra del vincolo di budget.
• $\nu^*$ è il prezzo ombra del vincolo di copertura.
• La regola tratta un individuo se il suo beneficio, aggiustato per il prezzo ombra della copertura, supera il costo scalato per il prezzo ombra del budget.

Questa struttura differisce dai problemi standard vincolati dal budget (che producono una semplice regola di rapporto $\tau(x)/c(x) \geq \lambda^*$) perché il vincolo di copertura introduce uno spostamento additivo ($\nu^*$), creando un confine decisionale eterogeneo.

2.2 Equivalenza con lo Zaino e Rilassamento LP

La controparte empirica del problema è mostrata essere equivalente a un problema dello zaino 0-1 con un vincolo di cardinalità aggiuntivo.

• Forma Combinatoria: Selezionare un vettore binario $d \in \{0,1\}^n$ per massimizzare $\sum \hat{\tau}_i d_i$ soggetto a $\sum c_i d_i \leq nC$ e $\sum d_i \geq n\rho$.
• Rilassamento di Programmazione Lineare (LP): Il vincolo binario è rilassato a $z_i \in [0,1]$.

Un risultato teorico critico è l'analisi del gap di interezza (la differenza tra il valore ottimo LP e il valore ottimo 0-1). Il documento dimostra che:

1. Ogni soluzione di punto estremo del rilassamento LP ha al massimo due componenti frazionarie.
2. Di conseguenza, il gap di interezza assoluto è limitato da una costante $O(1)$ (specificamente $2V_{max}$).
3. In termini pro capite, il gap svanisce asintoticamente come $O(1/n)$. Ciò implica che il rilassamento LP è asintoticamente equivalente alla soluzione discreta ottimale.

2.3 Algoritmi Implementabili

Sulla base del rilassamento LP e della struttura della soglia affine, vengono proposti due algoritmi:

1. Greedy–Lagrangiano con Copertura (GLC):

   • Meccanismo: Una ricerca primal-duale sul prezzo ombra del budget $\lambda$. Per un $\lambda$ fisso, le unità sono classificate in base a $a_i(\lambda) = \hat{\tau}_i - \lambda c_i$.
   • Procedura: L'algoritmo impone il vincolo di copertura forzando le $K_n$ unità superiori (minimo richiesto) per punteggio nell'insieme di trattamento, quindi aggiunge in modo greedy le unità rimanenti con punteggi positivi fino all'esaurimento del budget. Il moltiplicatore $\lambda$ è sintonizzato tramite bisezione per soddisfare il vincolo di budget.
   • Complessità: $O(n \log n \cdot \log(1/\varepsilon))$.

2. Rank-and-Cut (RC):

   • Meccanismo: Una regola euristica non iterativa che classifica le unità esclusivamente in base al rapporto costo-efficacia $s_i = \hat{\tau}_i / c_i$.
   • Procedura: Le unità sono ordinate per $s_i$ in ordine decrescente. L'algoritmo seleziona il prefisso più grande ammissibile che soddisfa sia il vincolo di budget che quello di copertura.
   • Complessità: $O(n \log n)$.

3. Risultati Chiave

3.1 Ottimalità Asintotica

Il documento stabilisce che l'algoritmo GLC è asintoticamente ottimale. Poiché il rilassamento LP ha un gap di interezza pro capite che svanisce, qualsiasi regola greedy ammissibile che approssima l'ottimo LP (come fa GLC) è anch'essa asintoticamente ottimale per il problema combinatorio originale.

3.2 Prestazioni di Rank-and-Cut (RC)

Il documento fornisce una caratterizzazione precisa di quando la regola RC più semplice è approssimativamente ottimale. La perdita di benessere di RC rispetto alla politica ottimale è guidata dalla discrepanza tra la soglia costante utilizzata da RC e la soglia affine eterogenea della politica ottimale.

• Condizione di Equivalenza: RC è approssimativamente ottimale se:
  1. I costi sono omogenei ($c(x) \approx c_0$), OPPURE
  2. Il vincolo di copertura è lasco ($\nu^* \approx 0$).
• Condizione di Errata Allocazione: Una significativa errata allocazione si verifica solo quando l'eterogeneità dei costi è sostanziale E il vincolo di copertura è vincolante ($\nu^* > 0$). In questo specifico regime, il confine affine della politica ottimale non può essere replicato da una semplice classificazione basata sul rapporto, portando al trattamento di unità a basso rapporto (per soddisfare la copertura) e all'esclusione di unità ad alto rapporto (a causa del budget).

3.3 Evidenza Monte Carlo

Due studi di simulazione supportano i risultati teorici:

1. GLC vs LP: All'aumentare della dimensione del campione $n$, il rimpianto pro capite di GLC rispetto alla soluzione ottimale esatta (MILP) diminuisce rapidamente, stabilizzandosi a livelli bassi. Anche il gap di interezza LP svanisce rapidamente, confermando la convergenza $O(1/n)$.
2. RC vs LP: Le simulazioni attraverso quattro regimi (variando l'eterogeneità dei costi e la rigidità della copertura) confermano che l'errata allocazione tra RC e la politica ottimale è trascurabile in tutti i casi tranne quando i costi sono eterogenei e la copertura è vincolante. In quello specifico scenario "peggiore", l'area di errata allocazione è significativa (~15%), validando l'effetto di interazione teorico.

4. Contributi e Significato

Il documento apporta tre contributi principali:

1. Rappresentazione Strutturale: Fornisce una caratterizzazione strutturale dell'apprendimento della politica vincolato come un problema di tipo zaino con una regola di soglia affine che coinvolge due prezzi ombra, modellando esplicitamente l'interazione tra vincoli di budget e copertura.
2. Strettezza Asintotica: Stabilisce che il rilassamento LP di questo problema combinatorio ha un gap di interezza $O(1)$, dimostrando l'equivalenza asintotica tra soluzioni rilassate e discrete in termini pro capite. Ciò giustifica l'uso di regole più semplici e scalabili in applicazioni su larga scala.
3. Implementazione e Limiti: Propone e analizza due algoritmi scalabili (GLC e RC). Crucialmente, identifica le precise condizioni strutturali sotto le quali la semplice regola RC non iterativa fallisce. Il documento colma il divario tra l'apprendimento statistico delle politiche e l'ottimizzazione combinatoria, offrendo un quadro che è sia teoricamente fondato che computazionalmente scalabile.

Il significato del lavoro risiede nella sua capacità di andare oltre la caratterizzazione teorica delle politiche ottimali per fornire soluzioni implementabili e scalabili con garanzie di prestazione. Chiarisce che, sebbene una semplice classificazione per costo-efficacia sia spesso sufficiente, i decisori politici devono essere consapevoli delle specifiche condizioni strutturali (costi eterogenei + copertura vincolante) in cui tali euristiche possono portare a significative perdite di benessere.