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

Resumen Técnico: Prescribir-Seleccionar (PS)

Configuración del Problema
El artículo aborda la Optimización Estocástica Contextual (CSO), una clase de problemas donde un tomador de decisiones observa covariables (contexto) $X$ antes de seleccionar una acción $z$ de un conjunto factible $Z$ para minimizar el costo esperado $E[c(z, Y) | X=x]$, donde $Y$ es una variable aleatoria incierta. Una restricción crítica en el escenario estudiado es que las decisiones deben satisfacer restricciones de factibilidad rígidas (que pueden incluir restricciones de integralidad) para cada realización del contexto.

Los autores identifican un desafío clave: en muchos escenarios de CSO, ninguna política candidata única domina uniformemente en todo el espacio de covariables. Diferentes paradigmas de modelado (por ejemplo, predicción puntual frente a estimación distribucional) a menudo exhiben rendimiento heterogéneo, sobresaliendo en regímenes específicos (por ejemplo, regiones de baja varianza frente a regiones de alta varianza) mientras que tienen un desempeño deficiente en otros. Los métodos existentes para la selección de políticas a menudo fallan en entornos con restricciones porque promediar políticas factibles no garantiza un resultado factible, y los enfoques de entrenamiento de extremo a extremo pueden sufrir cargas computacionales y una convergencia más lenta del arrepentimiento.

Metodología: Prescribir-Seleccionar (PS)
Los autores proponen Prescribir-Seleccionar (PS), un marco modular de dos etapas diseñado para seleccionar adaptativamente la mejor política para un contexto dado sin violar las restricciones de factibilidad.

1. Prescribir (Construcción de la Biblioteca):
   La primera etapa construye una biblioteca diversa de políticas candidatas factibles $\Pi_M = \{\pi_1, \dots, \pi_M\}$. Estas políticas mapean covariables a decisiones factibles bajo diferentes supuestos de modelado. El artículo utiliza tres familias de métodos:

   • Aproximación del Promedio de Muestras (SAA): Ignora las covariables, resolviendo una optimización determinista sobre escenarios históricos.
   • Políticas de Predicción Puntual (PPt): Ajusta un modelo predictivo (por ejemplo, kNN, Bosque Aleatorio, Red Neuronal) para estimar $E[Y|X]$ y resuelve una optimización determinista utilizando esta estimación puntual.
   • Políticas Predictivo-Prescriptivas (PP): Utiliza modelos predictivos (por ejemplo, kNN, Bosque Aleatorio) para generar pesos para una aproximación del promedio de muestras ponderada, aproximando efectivamente la distribución condicional $f_{Y|X}$.

2. Seleccionar (Aprendizaje de Meta-política):
   La segunda etapa aprende una meta-política para seleccionar la política candidata óptima para una covariable observada específica $x$.

   • Mecanismo: La meta-política se implementa utilizando un conjunto de Árboles de Política Óptima (OPT). A diferencia de las reglas de decisión paramétricas, los OPT dividen el espacio de covariables en regiones alineadas con los ejes y asignan un índice de política específico a cada región.
   • Entrenamiento: Los OPT se entrenan mediante validación cruzada K-fold. Para cada pliegue, las políticas candidatas se entrenan en la división de entrenamiento y se calculan sus costos fuera de muestra en el pliegue retenido para crear una "tabla de costos". Luego, el OPT se entrena para minimizar el costo empírico basado en esta tabla, aprendiendo efectivamente qué política funciona mejor en qué región del espacio de covariables.
   • Inferencia: En el momento de la inferencia, un conjunto de árboles (entrenados a través de pliegues y semillas aleatorias) vota para seleccionar el índice de política final, que luego se aplica para generar la decisión.

Contribuciones Clave

1. Formalización: El artículo define formalmente el problema de la selección de políticas en CSO bajo restricciones de factibilidad rígidas, un escenario donde el promediado de conjuntos estándar a menudo es inviable.
2. Marco: Introduce el marco Prescribir-Seleccionar, que desacopla la generación de políticas de la selección de políticas. Esto permite la integración de paradigmas de modelado diversos y potencialmente incompatibles, asegurando al mismo tiempo que la decisión final permanezca factible.
3. Selección Basada en Datos: El enfoque es completamente basado en datos, utilizando tablas de costos validadas cruzadamente para entrenar una meta-política (Árboles de Política Óptima) que aprende a particionar el espacio de covariables y asignar la política más efectiva a cada región.

Resultados Experimentales
Los autores evalúan PS en dos problemas de referencia: un problema de vendedor de periódicos de múltiples productos y un problema de planificación de envíos en dos etapas. Ambas tareas utilizan datos sintéticos con segmentos de demanda distintos (por ejemplo, picos festivos, tendencias estacionales) para inducir heterogeneidad.

• Heterogeneidad: Los experimentos confirman que ninguna política única domina uniformemente. El rendimiento varía significativamente entre segmentos y tamaños de entrenamiento (por ejemplo, los métodos de predicción puntual sobresalen en segmentos de baja varianza, mientras que los métodos predictivo-prescriptivos dominan en regímenes de alta varianza o discontinuos).
• Ganancias de Rendimiento: En regímenes heterogéneos, PS supera consistentemente a la mejor política candidata única. Las ganancias son estadísticamente significativas, particularmente cuando los datos de entrenamiento son limitados o cuando el espacio de covariables contiene regímenes distintos donde diferentes políticas son óptimas.
• Convergencia: En regímenes donde una sola política es uniformemente dominante (o a medida que el tamaño de entrenamiento $N$ se vuelve muy grande y una política emerge claramente como superior), PS converge a esa política dominante, incurriendo en un arrepentimiento insignificante en relación con la mejor política única.
• Eficiencia Computacional: La sobrecarga de entrenar la meta-política es mínima en comparación con el costo de resolver los problemas de optimización subyacentes para las políticas candidatas.

Significado y Afirmaciones
El artículo afirma que PS proporciona un enfoque práctico y de bajo riesgo para entornos de toma de decisiones donde están disponibles múltiples modelos prescriptivos de alta calidad. Al aprovechar la información contextual para seleccionar la política más adecuada para cada instancia, PS explota la heterogeneidad para mejorar sobre la mejor política única sin requerir un entrenamiento complejo de extremo a extremo ni violar las restricciones de factibilidad. El marco se presenta como una solución modular que puede integrar flexiblemente políticas diversas, adaptándose a entornos de decisión complejos donde un modelo de "talla única" es subóptimo. Los autores señalan que, aunque algunas políticas base son óptimas asintóticamente, PS ofrece beneficios significativos en configuraciones de muestras finitas al enrutar dinámicamente los contextos al modelo más efectivo.