Résumé technique : Apprentissage de politique optimale sous contraintes de budget et de couverture

1. Énoncé du problème

L'article aborde le problème de l'apprentissage de politique optimale dans des contextes où un décideur doit allouer une ressource limitée (traitement) à une population de $N$ unités afin de maximiser le bien-être total (gains espérés). Cette allocation est soumise à deux contraintes simultanées :

1. Contrainte de budget : Le coût total du traitement ne peut dépasser un budget fixe $B$ (ou un budget par habitant $C$).
2. Contrainte de couverture minimale : Une fraction minimale $\rho$ de la population doit être traitée.

Ce problème se pose dans des contextes tels que la formation à l'emploi publique, les interventions médicales ou les prestations sociales, où l'efficacité (maximisation des gains) doit être équilibrée avec l'équité ou les exigences politiques (garantir une large couverture). Le défi central réside dans le fait que la solution optimale nécessite la sélection d'un sous-ensemble d'unités parmi un ensemble exponentiellement grand d'alternatives ($2^N$), formant un problème d'optimisation combinatoire qui est NP-difficile.

2. Méthodologie et cadre théorique

2.1 Caractérisation primale-duale

L'auteur formule le problème dans le cadre des résultats potentiels. Soit $\tau(x)$ l'effet moyen du traitement conditionnel (CATE) et $c(x)$ le coût du traitement d'un individu ayant des covariables $x$. L'objectif est de maximiser $E[\pi(X)\tau(X)]$ sous les contraintes $E[\pi(X)c(X)] \leq C$ et $E[\pi(X)] \geq \rho$.

En utilisant la dualité lagrangienne, l'article établit que la politique optimale $\pi^*$ prend la forme d'une règle de seuil affine :
$$\pi^*(x) = \mathbb{1}\{ \tau(x) - \lambda^* c(x) + \nu^* \geq 0 \}$$
où :

• $\lambda^*$ est le prix fictif (shadow price) de la contrainte de budget.
• $\nu^*$ est le prix fictif de la contrainte de couverture.
• La règle traite un individu si son bénéfice, ajusté par le prix fictif de la couverture, dépasse le coût mis à l'échelle par le prix fictif du budget.

Cette structure diffère des problèmes standard sous contrainte de budget (qui aboutissent à une règle de ratio simple $\tau(x)/c(x) \geq \lambda^*$) car la contrainte de couverture introduit un décalage additif ($\nu^*$), créant une frontière de décision hétérogène.

2.2 Équivalence au problème du sac à dos et relaxation en PL

La contrepartie empirique du problème est montrée comme étant équivalente à un problème du sac à dos 0-1 avec une contrainte de cardinalité supplémentaire.

• Forme combinatoire : Sélectionner un vecteur binaire $d \in \{0,1\}^n$ pour maximiser $\sum \hat{\tau}_i d_i$ sous les contraintes $\sum c_i d_i \leq nC$ et $\sum d_i \geq n\rho$.
• Relaxation en Programmation Linéaire (PL) : La contrainte binaire est relâchée vers $z_i \in [0,1]$.

Un résultat théorique critique est l'analyse de l'écart d'intégralité (la différence entre la valeur optimale de la PL et la valeur optimale 0-1). L'article démontre que :

1. Toute solution de point extrême de la relaxation PL possède au maximum deux composantes fractionnaires.
2. Par conséquent, l'écart d'intégralité absolu est borné par une constante $O(1)$ (spécifiquement $2V_{max}$).
3. En termes par habitant, l'écart tend asymptotiquement vers zéro comme $O(1/n)$. Cela implique que la relaxation PL est asymptotiquement équivalente à la solution discrète optimale.

2.3 Algorithmes implémentables

Sur la base de la relaxation PL et de la structure de seuil affine, deux algorithmes sont proposés :

1. Glouton-Lagrangien avec Couverture (GLC) :

   • Mécanisme : Une recherche primale-duale sur le prix fictif du budget $\lambda$. Pour un $\lambda$ fixe, les unités sont notées selon $a_i(\lambda) = \hat{\tau}_i - \lambda c_i$.
   • Procédure : L'algorithme impose la contrainte de couverture en forçant les $K_n$ unités (minimum requis) ayant les meilleures notes dans l'ensemble des traitements, puis ajoute de manière gloutonne les unités restantes ayant des notes positives jusqu'à épuisement du budget. Le multiplicateur $\lambda$ est ajusté par dichotomie pour satisfaire la contrainte de budget.
   • Complexité : $O(n \log n \cdot \log(1/\varepsilon))$.

2. Classement et Troncature (RC) :

   • Mécanisme : Une règle heuristique non itérative qui classe les unités uniquement selon le ratio coût-efficacité $s_i = \hat{\tau}_i / c_i$.
   • Procédure : Les unités sont triées par $s_i$ dans l'ordre décroissant. L'algorithme sélectionne le plus grand préfixe réalisable satisfaisant à la fois les contraintes de budget et de couverture.
   • Complexité : $O(n \log n)$.

3. Résultats clés

3.1 Optimalité asymptotique

L'article établit que l'algorithme GLC est asymptotiquement optimal. Étant donné que la relaxation PL présente un écart d'intégralité par habitant tendant vers zéro, toute règle gloutonne réalisable qui approxime l'optimum de la PL (ce que fait GLC) est également asymptotiquement optimale pour le problème combinatoire original.

3.2 Performance du Classement et Troncature (RC)

L'article fournit une caractérisation précise des conditions dans lesquelles la règle RC plus simple est approximativement optimale. La perte de bien-être de RC par rapport à la politique optimale est pilotée par l'écart entre le seuil constant utilisé par RC et le seuil affine hétérogène de la politique optimale.

• Condition d'équivalence : RC est approximativement optimale si :
  1. Les coûts sont homogènes ($c(x) \approx c_0$), OU
  2. La contrainte de couverture est non contraignante ($\nu^* \approx 0$).
• Condition de mauvaise allocation : Une mauvaise allocation significative se produit uniquement lorsque l'hétérogénéité des coûts est substantielle ET que la contrainte de couverture est contraignante ($\nu^* > 0$). Dans ce régime spécifique, la frontière affine de la politique optimale ne peut pas être reproduite par un simple classement basé sur le ratio, conduisant au traitement d'unités à faible ratio (pour satisfaire la couverture) et à l'exclusion d'unités à fort ratio (en raison du budget).

3.3 Preuves par Monte Carlo

Deux études de simulation soutiennent les résultats théoriques :

1. GLC vs PL : À mesure que la taille de l'échantillon $n$ augmente, le regret par habitant de GLC par rapport à la solution optimale exacte (PLMI) diminue rapidement, se stabilisant à des niveaux faibles. L'écart d'intégralité de la PL disparaît également rapidement, confirmant la convergence en $O(1/n)$.
2. RC vs PL : Des simulations sur quatre régimes (variant l'hétérogénéité des coûts et la rigidité de la couverture) confirment que la mauvaise allocation entre RC et la politique optimale est négligeable dans tous les cas, sauf lorsque les coûts sont hétérogènes et que la couverture est contraignante. Dans ce scénario spécifique de « pire cas », la zone de mauvaise allocation est significative (~15 %), validant l'effet d'interaction théorique.

4. Contributions et signification

L'article apporte trois contributions principales :

1. Représentation structurelle : Il fournit une caractérisation structurelle de l'apprentissage de politique contraint comme un problème de type sac à dos avec une règle de seuil affine impliquant deux prix fictifs, modélisant explicitement l'interaction entre les contraintes de budget et de couverture.
2. Précision asymptotique : Il établit que la relaxation PL de ce problème combinatoire présente un écart d'intégralité en $O(1)$, prouvant l'équivalence asymptotique entre les solutions relâchées et discrètes en termes par habitant. Cela justifie l'utilisation de règles plus simples et évolutives dans des applications à grande échelle.
3. Implémentation et limites : Il propose et analyse deux algorithmes évolutifs (GLC et RC). Crucialement, il identifie les conditions structurelles précises sous lesquelles la règle RC simple et non itérative échoue. L'article comble le fossé entre l'apprentissage de politique statistique et l'optimisation combinatoire, offrant un cadre à la fois théoriquement fondé et évolutif en termes de calcul.

La signification de ce travail réside dans sa capacité à dépasser la caractérisation théorique des politiques optimales pour fournir des solutions implémentables et évolutives avec des garanties de performance. Il clarifie que si un classement simple par coût-efficacité est souvent suffisant, les décideurs politiques doivent être conscients des conditions structurelles spécifiques (coûts hétérogènes + couverture contraignante) où de telles heuristiques peuvent entraîner des pertes de bien-être significatives.