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

Resumo Técnico: Prescrever-e-Selecionar (PS)

Configuração do Problema
O artigo aborda a Otimização Estocástica Contextual (CSO), uma classe de problemas em que um tomador de decisão observa covariáveis (contexto) $X$ antes de selecionar uma ação $z$ de um conjunto viável $Z$ para minimizar o custo esperado $E[c(z, Y) | X=x]$, onde $Y$ é uma variável aleatória incerta. Uma restrição crítica no cenário estudado é que as decisões devem satisfazer restrições de viabilidade rígidas (que podem incluir restrições de integralidade) para cada realização do contexto.

Os autores identificam um desafio fundamental: em muitos cenários de CSO, nenhuma política candidata única domina uniformemente em todo o espaço de covariáveis. Diferentes paradigmas de modelagem (por exemplo, previsão pontual versus estimação distribucional) frequentemente exibem desempenho heterogêneo, destacando-se em regimes específicos (por exemplo, regiões de baixa variância versus regiões de alta variância) enquanto têm desempenho inferior em outros. Métodos existentes para seleção de políticas frequentemente falham em cenários com restrições, pois a média de políticas viáveis não garante um resultado viável, e abordagens de treinamento ponta a ponta podem sofrer com ônus computacionais e convergência mais lenta do arrependimento.

Metodologia: Prescrever-e-Selecionar (PS)
Os autores propõem o Prescrever-e-Selecionar (PS), um framework modular de duas etapas projetado para selecionar adaptativamente a melhor política para um dado contexto sem violar restrições de viabilidade.

1. Prescrever (Construção da Biblioteca):
   A primeira etapa constrói uma biblioteca diversificada de políticas candidatas viáveis $\Pi_M = \{\pi_1, \dots, \pi_M\}$. Essas políticas mapeiam covariáveis para decisões viáveis sob diferentes suposições de modelagem. O artigo utiliza três famílias de métodos:

   • Aproximação Média Amostral (SAA): Ignora covariáveis, resolvendo uma otimização determinística sobre cenários históricos.
   • Políticas de Previsão Pontual (PPt): Ajusta um modelo preditivo (por exemplo, kNN, Floresta Aleatória, Rede Neural) para estimar $E[Y|X]$ e resolve uma otimização determinística usando essa estimativa pontual.
   • Políticas Preditivo-Prescritivas (PP): Utiliza modelos preditivos (por exemplo, kNN, Floresta Aleatória) para gerar pesos para uma aproximação média amostral ponderada, aproximando efetivamente a distribuição condicional $f_{Y|X}$.

2. Selecionar (Aprendizado de Meta-política):
   A segunda etapa aprende uma meta-política para selecionar a política candidata ótima para uma covariável observada específica $x$.

   • Mecanismo: A meta-política é implementada usando um ensemble de Árvores de Política Ótima (OPT). Diferentemente de regras de decisão paramétricas, as OPTs particionam o espaço de covariáveis em regiões alinhadas aos eixos e atribuem um índice de política específico a cada região.
   • Treinamento: As OPTs são treinadas via validação cruzada K-fold. Para cada dobra, as políticas candidatas são treinadas na divisão de treinamento, e seus custos fora da amostra são computados na dobra retida para criar uma "tabela de custos". A OPT é então treinada para minimizar o custo empírico com base nessa tabela, aprendendo efetivamente qual política performa melhor em qual região do espaço de covariáveis.
   • Inferência: No momento da inferência, um ensemble de árvores (treinado em dobras e sementes aleatórias) vota para selecionar o índice final da política, que é então aplicado para gerar a decisão.

Principais Contribuições

1. Formalização: O artigo define formalmente o problema de seleção de políticas em CSO sob restrições de viabilidade rígidas, um cenário onde a média de ensemble padrão é frequentemente inviável.
2. Framework: Introduz o framework Prescrever-e-Selecionar, que desacopla a geração de políticas da seleção de políticas. Isso permite a integração de paradigmas de modelagem diversos e potencialmente incompatíveis, enquanto garante que a decisão final permaneça viável.
3. Seleção Baseada em Dados: A abordagem é inteiramente baseada em dados, utilizando tabelas de custo validadas cruzadamente para treinar uma meta-política (Árvores de Política Ótima) que aprende a particionar o espaço de covariáveis e atribuir a política mais eficaz a cada região.

Resultados Experimentais
Os autores avaliam o PS em dois problemas de referência: um problema de vendedor de jornais multi-produto e um problema de planejamento de embarque em duas etapas. Ambas as tarefas utilizam dados sintéticos com segmentos distintos de demanda (por exemplo, picos de feriados, tendências sazonais) para induzir heterogeneidade.

• Heterogeneidade: Os experimentos confirmam que nenhuma política única domina uniformemente. O desempenho varia significativamente entre segmentos e tamanhos de treinamento (por exemplo, métodos de previsão pontual destacam-se em segmentos de baixa variância, enquanto métodos preditivo-prescritivos dominam em regimes de alta variância ou descontínuos).
• Ganhos de Desempenho: Em regimes heterogêneos, o PS supera consistentemente a melhor política candidata única. Os ganhos são estatisticamente significativos, particularmente quando os dados de treinamento são limitados ou quando o espaço de covariáveis contém regimes distintos onde diferentes políticas são ótimas.
• Convergência: Em regimes onde uma única política é uniformemente dominante (ou à medida que o tamanho do treinamento $N$ torna-se muito grande e uma política emerge claramente como superior), o PS converge para essa política dominante, incorrendo em arrependimento negligenciável em relação à melhor política única.
• Eficiência Computacional: O custo adicional de treinar a meta-política é mínimo em comparação ao custo de resolver os problemas de otimização subjacentes para as políticas candidatas.

Significado e Afirmações
O artigo afirma que o PS fornece uma abordagem prática e de baixo risco para ambientes de tomada de decisão onde múltiplos modelos prescritivos de alta qualidade estão disponíveis. Ao aproveitar informações contextuais para selecionar a política mais adequada para cada instância, o PS explora a heterogeneidade para melhorar o desempenho sobre a melhor política única, sem exigir treinamento complexo ponta a ponta ou violar restrições de viabilidade. O framework é apresentado como uma solução modular que pode integrar flexivelmente políticas diversas, adaptando-se a ambientes de decisão complexos onde um modelo "tamanho único" é subótimo. Os autores observam que, embora algumas políticas base sejam assintoticamente ótimas, o PS oferece benefícios significativos em cenários de amostra finita ao rotear dinamicamente contextos para o modelo mais eficaz.