Wasserstein Distributionally Robust Regret Optimization

Resumo Técnico: Otimização de Regret de Distribuição Robusta de Wasserstein

Enunciado do Problema
A tomada de decisão sob incerteza frequentemente baseia-se na Minimização do Risco Empírico (ERM), que assume que a distribuição empírica representa o ambiente de implementação. Embora a ERM ofereça garantias robustas fora da amostra sob suposições de suavidade e i.i.d., ela pode falhar quando as distribuições de treinamento e implementação divergem. A Otimização de Distribuição Robusta (DRO) aborda isso minimizando a perda de pior caso sobre um conjunto de ambiguidade (tipicamente uma bola de Wasserstein). No entanto, o foco adversarial da DRO no pior caso de perda pode levar a políticas excessivamente conservadoras, particularmente em configurações com potencial de upside assimétrico (ex: estoque de baixo custo e alta margem), onde a supressão de resultados favoráveis é subótima.

Para mitigar esse excesso de conservadorismo, este artigo estuda a Otimização de Regret de Distribuição Robusta ex-ante (DRRO). Diferente do regret ex-post (que compara uma política com a melhor decisão para cada realização específica de incerteza) ou da DRO padrão (que minimiza a perda de pior caso), a DRRO ex-ante minimiza o regret de pior caso sobre um conjunto de ambiguidade. O regret é definido como a diferença entre a perda esperada de uma política e a perda esperada da política ótima para aquela distribuição específica. O artigo foca na DRRO de Wasserstein (WDRRO), utilizando conjuntos de ambiguidade de tipo-$p$ centrados em uma distribuição de referência empírica.

Metodologia e Estrutura Teórica
O artigo desenvolve uma teoria estrutural e computacional de WDRRO, organizada em torno de uma dicotomia entre regimes "regulares" (onde a ERM é suficiente) e regimes "complexos" (onde a WDRRO oferece vantagens distintas).

1. Teoria de Sensibilidade e Seleção de ERM:

   • Otimizador ERM Único: Sob condições de suavidade e regularidade com um otimizador ERM único, o artigo prova que a WDRRO possui sensibilidade de primeira ordem zero em relação ao raio de Wasserstein $\delta$. Especificamente, decisões quase ótimas de WDRRO satisfazem $\theta_\delta = \theta_{ERM} + o(\delta)$. Isso contrasta com a DRO de Wasserstein padrão, que tipicamente se afasta da ERM à ordem de $O(\delta)$.
   • Otimizador ERM Não Único: Quando o conjunto de soluções ERM não é único, a WDRRO atua como um regularizador, selecionando ótimos de ERM que minimizam a discrepância de gradiente de pior caso contra outras soluções de ERM (um jogo minimax de discrepância de gradiente).
   • Perdas Quadráticas: Para perdas quadráticas estritamente convexas com ordem de Wasserstein $p \ge 2$, o artigo estabelece que a política ERM é exatamente WDRRO-ótima para qualquer raio $\delta$, não apenas assintoticamente.

2. Regimes Computacionais e Complexidade:

   • O artigo identifica que a WDRRO torna-se computacionalmente frágil quando as suposições falham (ex: perdas não suaves, raios grandes).
   • NP-Dureza: Os autores provam que avaliar o regret de WDRRO é NP-difícil mesmo para perdas max-afins simples sem termos bilineares, utilizando distância de Wasserstein tipo-1 e uma norma de base $\ell_1$. Essa dureza persiste mesmo quando o risco de Wasserstein interno é tratável, distinguindo a WDRRO da WDRO padrão, RO e RRO, que permanecem tratáveis para as mesmas classes de perda.

3. Soluções Algorítmicas:

   • Algoritmos Exatos: Para instâncias de tamanho moderado, o artigo deriva uma formulação não convexa finita do regret usando dualidade de Wasserstein. Isso serve como um benchmark de verdade fundamental (ground-truth).
   • Relaxações Convexas: Para lidar com problemas maiores, os autores desenvolvem relaxações convexas tratáveis.
     • Para perdas sem termos bilineares ($d_k=0$), eles derivam um único programa convexo que limita superiormente o regret ex-post. Esta relaxação é exata em $\delta=0$ e em raios maiores que o diâmetro do suporte, com um gap de aproximação de $O(\delta)$.
     • Para perdas com termos bilineares ($d_k \neq 0$), eles propõem uma extensão de cobertura local. Ao cobrir o espaço de decisão com centros de referência, eles aproximam os termos cruzados, introduzindo um termo de erro adicional dependente do raio de cobertura $\rho$ (especificamente $O(\rho \delta)$).

Principais Resultados e Experimentos
O artigo valida sua teoria e algoritmos através de experimentos numéricos em problemas de newsvendor e alocação de portfólio média-CVaR:

• Problema do Newsvendor:

  • Em um cenário de baixo custo e alta margem, a política de DRRO torna-se mais agressiva conforme o raio de incerteza aumenta, enquanto a DRO se torna mais conservadora. Isso captura o potencial de "upside" que a DRO suprime.
  • Em um cenário de alto custo, a DRRO torna-se mais conservadora, demonstrando que a direção da resposta da DRRO depende da assimetria do payoff.
  • A relaxação convexa proposta acompanha de perto a solução exata de WDRRO, com gaps negligenciáveis em quantidades de pedido e regret.
    im de termos de computação, a relaxação proposta escala eficientemente para grandes volumes de amostras, enquanto uma relaxação concorrente (Cho e Yang [14]) torna-se intratável (NP-difícil) conforme o tamanho da amostra aumenta.

• Otimização de Portfólio (Média-CVaR):

  • Em um cenário de ativo único, a DRO exibe um comportamento descontínuo de "tudo ou nada" (saltando de investimento total para zero investimento) conforme o raio aumenta. Em contraste, as políticas de DRRO exibem comportamento não monótono, ajustando gradualmente a exposição para equilibrar o regret contra distribuições adversas.
  • Em cenários de múltiplos ativos, a relaxação de DRRO mantém exposição positiva a ativos de risco por um intervalo de raios maior do que a DRO, que eventualmente migra totalmente para o ativo livre de risco.
  • A análise teórica sugere que, para raios muito grandes, as políticas de regret-ótimas convergem para o investimento total em ativos de risco (devido ao upside ilimitado), enquanto a DRO converge para o ativo livre de risco.

Significância e Alegações
O artigo afirma fornecer a primeira teoria abrangente e estrutura computacional para WDRRO. Suas principais contribuições são:

1. Insight Teórico: Estabelecer que em regimes regulares (perdas suaves, ERM único), a robustificação baseada em regret é desnecessária, pois a ERM já é de primeira ordem ótima. O valor da WDRRO emerge principalmente em regimes não suaves ou de raio grande.
2. Separação de Complexidade: Demonstrar que a WDRRO é computacionalmente mais difícil do que formulações robustas padrão (WDRO, RO, RRO) para perdas max-afins, especificamente devido à maximização externa sobre a decisão de benchmark.
3. Algoritmos Práticos: Fornecer os primeiros algoritmos exatos para avaliação de WDRRO e uma nova classe de relaxações convexas que são tratáveis, escaláveis e oferecem garantias de raio finito.
4. Nuance Comportamental: Mostrar que a DRRO pode capturar comportamentos agressivos ou conservadores dependentes da perda que a DRO de pior caso de perda (worst-case loss) não capta.

Os autores concluem que, embora a ERM seja suficiente em regimes benignos, a WDRRO é uma ferramenta necessária para lidar com a especificação errônea de distribuição em cenários complexos, não suaves ou de alto risco, desde que se utilizem as relaxações desenvolvidas para gerenciar a complexidade computacional.