Prescribe-then-Select: Adaptive Policy Selection for Contextual Stochastic Optimization

Résumé technique : Prescrire puis Sélectionner (PS)

Cadre du problème
L'article traite de l'optimisation stochastique contextuelle (CSO), une classe de problèmes où un décideur observe des covariables (contexte) $X$ avant de sélectionner une action $z$ dans un ensemble réalisable $Z$ afin de minimiser le coût attendu $E[c(z, Y) | X=x]$, où $Y$ est une variable aléatoire incertaine. Une contrainte critique dans le cadre étudié est que les décisions doivent satisfaire des contraintes de faisabilité rigides (qui peuvent inclure des contraintes d'intégralité) pour chaque réalisation du contexte.

Les auteurs identifient un défi clé : dans de nombreux cadres CSO, aucune politique candidate unique ne domine uniformément sur l'ensemble de l'espace des covariables. Différents paradigmes de modélisation (par exemple, prédiction ponctuelle vs estimation distributionnelle) présentent souvent des performances hétérogènes, excellant dans des régimes spécifiques (par exemple, régions à faible variance vs régions à haute variance) tout en sous-performant dans d'autres. Les méthodes existantes de sélection de politique échouent souvent dans des cadres contraints car la moyenne de politiques réalisables ne garantit pas un résultat réalisable, et les approches d'entraînement de bout en bout peuvent souffrir de lourdeurs computationnelles et d'une convergence plus lente du regret.

Méthodologie : Prescrire puis Sélectionner (PS)
Les auteurs proposent Prescrire puis Sélectionner (PS), un cadre modulaire en deux étapes conçu pour sélectionner de manière adaptative la meilleure politique pour un contexte donné sans violer les contraintes de faisabilité.

1. Prescrire (Construction de la bibliothèque) :
   La première étape construit une bibliothèque diversifiée de politiques candidates réalisables $\Pi_M = \{\pi_1, \dots, \pi_M\}$. Ces politiques mappent les covariables vers des décisions réalisables sous différentes hypothèses de modélisation. L'article utilise trois familles de méthodes :

   • Approximation par Moyenne Échantillonnale (SAA) : Ignore les covariables, résolvant une optimisation déterministe sur des scénarios historiques.
   • Politiques de Prédiction Ponctuelle (PPt) : Ajuste un modèle prédictif (par exemple, kNN, Forêt Aléatoire, Réseau de Neurones) pour estimer $E[Y|X]$ et résout une optimisation déterministe en utilisant cette estimation ponctuelle.
   • Politiques Prédictives-Préscriptives (PP) : Utilise des modèles prédictifs (par exemple, kNN, Forêt Aléatoire) pour générer des poids pour une approximation par moyenne échantillonnale pondérée, approximent ainsi efficacement la distribution conditionnelle $f_{Y|X}$.

2. Sélectionner (Apprentissage de la méta-politique) :
   La deuxième étape apprend une méta-politique pour sélectionner la politique candidate optimale pour une covariable observée spécifique $x$.

   • Mécanisme : La méta-politique est mise en œuvre à l'aide d'un ensemble d'Arbres de Politiques Optimales (OPT). Contrairement aux règles de décision paramétriques, les OPT partitionnent l'espace des covariables en régions alignées sur les axes et attribuent un indice de politique spécifique à chaque région.
   • Entraînement : Les OPT sont entraînés par validation croisée K-fold. Pour chaque pli, les politiques candidates sont entraînées sur la partition d'entraînement, et leurs coûts hors échantillon sont calculés sur le pli retenu pour créer un « tableau de coûts ». L'OPT est ensuite entraîné pour minimiser le coût empirique basé sur ce tableau, apprenant ainsi quelle politique performe le mieux dans quelle région de l'espace des covariables.
   • Inférence : Au moment de l'inférence, un ensemble d'arbres (entraînés sur différents plis et graines aléatoires) vote pour sélectionner l'indice de politique final, qui est ensuite appliqué pour générer la décision.

Contributions clés

1. Formalisation : L'article définit formellement le problème de sélection de politique en CSO sous contraintes de faisabilité rigides, un cadre où la moyenne d'ensemble standard est souvent irréalisable.
2. Cadre : Il introduit le cadre Prescrire puis Sélectionner, qui découple la génération de politique de la sélection de politique. Cela permet l'intégration de paradigmes de modélisation divers, potentiellement incompatibles, tout en garantissant que la décision finale reste réalisable.
3. Sélection pilotée par les données : L'approche est entièrement pilotée par les données, utilisant des tableaux de coûts validés par croisée pour entraîner une méta-politique (Arbres de Politiques Optimales) qui apprend à partitionner l'espace des covariables et à attribuer la politique la plus efficace à chaque région.

Résultats expérimentaux
Les auteurs évaluent PS sur deux problèmes de référence : un problème de nouvelles-vendeuses multi-produits et un problème de planification d'expédition à deux étapes. Les deux tâches utilisent des données synthétiques avec des segments de demande distincts (par exemple, pics de vacances, tendances saisonnières) pour induire de l'hétérogénéité.

• Hétérogénéité : Les expériences confirment qu'aucune politique unique ne domine uniformément. Les performances varient considérablement selon les segments et les tailles d'entraînement (par exemple, les méthodes de prédiction ponctuelle excellent dans les segments à faible variance, tandis que les méthodes prédictives-préscriptives dominent dans les régimes à haute variance ou discontinus).
• Gains de performance : Dans les régimes hétérogènes, PS surpasse constamment la meilleure politique candidate unique. Les gains sont statistiquement significatifs, en particulier lorsque les données d'entraînement sont limitées ou lorsque l'espace des covariables contient des régimes distincts où différentes politiques sont optimales.
• Convergence : Dans les régimes où une politique unique est uniformément dominante (ou lorsque la taille d'entraînement $N$ devient très grande et qu'une politique émerge clairement comme supérieure), PS converge vers cette politique dominante, engendrant un regret négligeable par rapport à la meilleure politique unique.
• Efficacité computationnelle : La surcharge liée à l'entraînement de la méta-politique est minime par rapport au coût de résolution des problèmes d'optimisation sous-jacents pour les politiques candidates.

Signification et affirmations
L'article affirme que PS fournit une approche pratique et à faible risque pour les environnements de prise de décision où plusieurs modèles prescriptifs de haute qualité sont disponibles. En exploitant l'information contextuelle pour sélectionner la politique la plus adaptée à chaque instance, PS exploite l'hétérogénéité pour améliorer la meilleure politique unique sans nécessiter d'entraînement complexe de bout en bout ni violer les contraintes de faisabilité. Le cadre est présenté comme une solution modulaire capable d'intégrer de manière flexible des politiques diverses, s'adaptant à des environnements de décision complexes où un modèle « unique pour tous » est sous-optimal. Les auteurs notent que bien que certaines politiques de base soient asymptotiquement optimales, PS offre des avantages significatifs dans des contextes à échantillon fini en acheminant dynamiquement les contextes vers le modèle le plus efficace.