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

Riepilogo Tecnico: Prescrivere-poi-Selezionare (PS)

Impostazione del Problema
Il documento affronta l'Ottimizzazione Stocastica Contestuale (CSO), una classe di problemi in cui un decisore osserva le covariate (contesto) $X$ prima di selezionare un'azione $z$ da un insieme ammissibile $Z$ per minimizzare il costo atteso $E[c(z, Y) | X=x]$, dove $Y$ è una variabile aleatoria incerta. Un vincolo critico nell'impostazione studiata è che le decisioni devono soddisfare vincoli di ammissibilità rigidi (che possono includere vincoli di interezza) per ogni realizzazione del contesto.

Gli autori identificano una sfida chiave: in molti contesti CSO, nessuna singola politica candidata domina uniformemente su tutto lo spazio delle covariate. Paradigmi di modellazione diversi (ad esempio, previsione puntuale vs. stima distribuzionale) spesso mostrano prestazioni eterogenee, eccellendo in regimi specifici (ad esempio, regioni a bassa varianza vs. regioni ad alta varianza) mentre performano peggio in altri. I metodi esistenti per la selezione delle politiche spesso falliscono in contesti vincolati perché la media di politiche ammissibili non garantisce un risultato ammissibile, e gli approcci di addestramento end-to-end possono soffrire di oneri computazionali e una convergenza più lenta del rimpianto.

Metodologia: Prescrivere-poi-Selezionare (PS)
Gli autori propongono Prescrivere-poi-Selezionare (PS), un framework modulare a due fasi progettato per selezionare adattivamente la migliore politica per un dato contesto senza violare i vincoli di ammissibilità.

1. Prescrivere (Costruzione della Libreria):
   La prima fase costruisce una libreria diversificata di politiche candidate ammissibili $\Pi_M = \{\pi_1, \dots, \pi_M\}$. Queste politiche mappano le covariate in decisioni ammissibili sotto diverse ipotesi di modellazione. Il documento utilizza tre famiglie di metodi:

   • Approssimazione della Media Campionaria (SAA): Ignora le covariate, risolvendo un'ottimizzazione deterministica su scenari storici.
   • Politiche di Previsione Puntuale (PPt): Adatta un modello predittivo (ad esempio, kNN, Random Forest, Rete Neurale) per stimare $E[Y|X]$ e risolve un'ottimizzazione deterministica utilizzando questa stima puntuale.
   • Politiche Predittivo-Prescrittive (PP): Utilizza modelli predittivi (ad esempio, kNN, Random Forest) per generare pesi per un'approssimazione della media campionaria pesata, approssimando efficacemente la distribuzione condizionata $f_{Y|X}$.

2. Selezionare (Apprendimento della Meta-Politica):
   La seconda fase apprende una meta-politica per selezionare la politica candidata ottimale per una specifica covariate osservata $x$.

   • Meccanismo: La meta-politica è implementata utilizzando un ensemble di Alberi di Politica Ottimale (OPT). A differenza delle regole decisionali parametriche, gli OPT partizionano lo spazio delle covariate in regioni allineate agli assi e assegnano un indice di politica specifico a ciascuna regione.
   • Addestramento: Gli OPT sono addestrati tramite validazione incrociata K-fold. Per ogni fold, le politiche candidate sono addestrate sulla divisione di addestramento e i loro costi fuori campione sono calcolati sul fold tenuto da parte per creare una "tabella dei costi". L'OPT viene quindi addestrato per minimizzare il costo empirico basato su questa tabella, imparando efficacemente quale politica performa meglio in quale regione dello spazio delle covariate.
   • Inferenza: Al momento dell'inferenza, un ensemble di alberi (addestrati attraverso fold e semi casuali) vota per selezionare l'indice della politica finale, che viene quindi applicato per generare la decisione.

Contributi Chiave

1. Formalizzazione: Il documento definisce formalmente il problema della selezione delle politiche in CSO sotto vincoli di ammissibilità rigidi, un contesto in cui la media di ensemble standard è spesso non fattibile.
2. Framework: Introduce il framework Prescrivere-poi-Selezionare, che disaccoppia la generazione delle politiche dalla selezione delle politiche. Ciò consente l'integrazione di paradigmi di modellazione diversi e potenzialmente incompatibili, garantendo al contempo che la decisione finale rimanga ammissibile.
3. Selezione Guidata dai Dati: L'approccio è interamente guidato dai dati, utilizzando tabelle di costo validate incrociatamente per addestrare una meta-politica (Alberi di Politica Ottimale) che impara a partizionare lo spazio delle covariate e assegnare la politica più efficace a ciascuna regione.

Risultati Sperimentali
Gli autori valutano PS su due problemi di riferimento: un problema newsvendor multi-prodotto e un problema di pianificazione delle spedizioni a due stadi. Entrambi i compiti utilizzano dati sintetici con segmenti di domanda distinti (ad esempio, picchi festivi, tendenze stagionali) per indurre eterogeneità.

• Eterogeneità: Gli esperimenti confermano che nessuna singola politica domina uniformemente. Le prestazioni variano significativamente tra i segmenti e le dimensioni di addestramento (ad esempio, i metodi di previsione puntuale eccellono nei segmenti a bassa varianza, mentre le politiche predittivo-prescrittive dominano in regimi ad alta varianza o discontinui).
• Guadagni di Prestazione: In regimi eterogenei, PS supera costantemente la migliore singola politica candidata. I guadagni sono statisticamente significativi, in particolare quando i dati di addestramento sono limitati o quando lo spazio delle covariate contiene regimi distinti in cui politiche diverse sono ottimali.
• Convergenza: In regimi in cui una singola politica è uniformemente dominante (o quando la dimensione di addestramento $N$ diventa molto grande e emerge chiaramente una politica superiore), PS converge a quella politica dominante, sostenendo un rimpianto trascurabile rispetto alla migliore singola politica.
• Efficienza Computazionale: Il sovraccarico dell'addestramento della meta-politica è minimo rispetto al costo di risolvere i problemi di ottimizzazione sottostanti per le politiche candidate.

Significato e Affermazioni
Il documento afferma che PS fornisce un approccio pratico e a basso rischio per ambienti decisionali in cui sono disponibili molteplici modelli prescrittivi di alta qualità. Sfruttando le informazioni contestuali per selezionare la politica più adatta per ogni istanza, PS sfrutta l'eterogeneità per migliorare la migliore singola politica senza richiedere un addestramento end-to-end complesso o violare i vincoli di ammissibilità. Il framework è presentato come una soluzione modulare che può integrare flessibilmente politiche diverse, adattandosi a ambienti decisionali complessi in cui un modello "taglia unica" è subottimale. Gli autori notano che, sebbene alcune politiche di base siano asintoticamente ottimali, PS offre benefici significativi in contesti con campioni finiti instradando dinamicamente i contesti al modello più efficace.