Wasserstein Distributionally Robust Regret Optimization

Resumen Técnico: Optimización de Arrepentimiento Robusto con Distribución de Wasserstein

Planteamiento del Problema
La toma de decisiones bajo incertidumbre a menudo depende de la Minimización del Riesgo Empírico (ERM, por sus siglas en inglés), la cual asume que la distribución empírica representa el entorno de despliegue. Si bien la ERM ofrece sólidas garantías fuera de la muestra bajo supuestos de suavidad e i.i.d., puede fallar cuando las distribuciones de entrenamiento y despliegue divergen. La Optimización Robusta Distribucional (DRO) aborda esto minimizando la pérdida en el peor de los casos sobre un conjunto de ambigüedad (típicamente una bola de Wasserstein). Sin embargo, el enfoque adversarial de la DRO hacia la pérdida en el peor de los casos puede conducir a políticas excesivamente conservadoras, particularmente en entornos con un potencial de beneficio asimétrico (por ejemplo, inventario de bajo costo y alto margen), donde suprimir los resultados favorables es subóptimo.

Para mitigar este exceso de conservadurismo, este artículo estudia la Optimización de Arrepentimiento Robusto Distribucional ex-ante (DRRO). A diferencia del arrepentimiento ex-post (que compara una política con la mejor decisión para cada realización específica de la incertidumbre) o la DRO estándar (que minimiza la pérdida en el peor de los casos), la DRRO ex-ante minimiza el arrepentimiento en el peor de los casos sobre un conjunto de ambigüedad. El arrepentimiento se define como la diferencia entre la pérdida esperada de una política y la pérdida esperada de la política óptima para esa distribución específica. El artículo se centra en la DRRO de Wasserstein (WDRRO), utilizando conjuntos de ambigüedad de tipo-$p$ centrados en una distribución de referencia empírica.

Metodología y Marco Teórico
El artículo desarrolla una teoría estructural y computacional de la WDRRO, organizada en torno a una dicotomía entre regímenes "regulares" donde la ERM es suficiente y regímenes "complejos" donde la WDRRO ofrece ventajas distintivas.

1. Teoría de Sensibilidad y Selección de ERM:

   • Optimizador ERM Único: Bajo condiciones de suavidad y regularidad con un optimizador ERM único, el artículo demuestra que la WDRRO tiene sensibilidad de primer orden cero respecto al radio de Wasserstein $\delta$. Específicamente, las decisiones casi óptimas de la WDRRO satisfacen $\theta_\delta = \theta_{ERM} + o(\delta)$. Esto contrasta con la DRO de Wasserstein estándar, que típicamente se desplaza de la ERM a un orden de $O(\delta)$.
   • Optimizador ERM No Único: Cuando el conjunto de soluciones ERM no es único, la WDRRO actúa como un regularizador, seleccionando los óptimos de la ERM que minimizan la discrepancia de gradiente en el peor de los casos contra otras soluciones de la ERM (un juego de minimax de discrepancia de gradientes).
   • Pérdidas Cuadráticas: Para pérdidas cuadráticas estrictamente convexas con orden de Wasserstein $p \ge 2$, el artículo establece que la política ERM es exactamente óptima para la WDRRO para cualquier radio $\delta$, no solo asintóticamente.

2. Regímenes Computacionales y Dificultad:

   • El artículo identifica que la WDRRO se vuelve computacionalmente frágil cuando fallan los supuestos (por ejemplo, pérdidas no suaves, radios grandes).
   • NP-Dureza: Los autores demuestran que evaluar el arrepentimiento de la WDRRO es NP-duro incluso para pérdidas max-afines simples sin términos bilineales, utilizando la distancia de Wasserstein tipo-1 y una norma base $\ell_1$. Esta dificultad persiste incluso cuando el riesgo de Wasserstein interno es tratable, distinguiendo a la WDRRO de la WDRO estándar, la Optimización Robusta (RO) y la Optimización de Arrepentimiento Robusto (RRO), las cuales permanecen tratables para las mismas clases de pérdida.

3. Soluciones Algorítmicas:

   • Algoritmos Exactos: Para instancias de tamaño moderado, el artículo deriva una formulación no convexa finita del arrepentimiento utilizando la dualidad de Wasserstein. Esto sirve como un punto de referencia de verdad fundamental (ground-truth).
   • Relajaciones Convexas: Para manejar problemas más grandes, los autores desarrollan relajaciones convexas tratables.
     • Para pérdidas sin términos bilineales ($d_k=0$), derivan un único programa convexo que acota superiormente el arrepentimiento ex-post. Esta relajación es exacta en $\delta=0$ y en radios mayores que el diámetro del soporte, con una brecha de aproximación de $O(\delta)$.
     • Para pérdidas con términos bilineales ($d_k \neq 0$), proponen una extensión de cobertura local. Al cubrir el espacio de decisión con centros de referencia, aproximan los términos cruzados, introduciendo un término de error adicional dependiente del radio de cobertura $\rho$ (específicamente $O(\rho \delta)$).

Resultos Clave y Experimentos
El artículo valida su teoría y algoritmos mediante experimentos numéricos en problemas de vendedor de periódicos (newsvendor) y asignación de carteras media-CVaR:

• Problema del Vendedor de Periódicos (Newsvendor):

  • En un entorno de bajo costo y alto margen, la política de DRRO se vuelve más agresiva a medida que aumenta el radio de incertidumbre, mientras que la DRO se vuelve más conservadora. Esto captura el potencial de "alza" que la DRO suprime.
  • En un entorno de alto costo, la DRRO se vuelve más conservadora, demostrando que la dirección de la respuesta de la DRRO depende de la asimetría del beneficio.
  • La relajación convexa propuesta sigue de cerca la solución exacta de la WDRRO, con brechas insignificantes en las cantidades de pedido y el arrepentimiento.
  • En términos de computación, la relajación propuesta escala eficientemente a grandes tamaños de muestra, mientras que una relajación competidora (Cho y Yang [14]) se vuelve intratable (NP-dura) a medida que el tamaño de la muestra aumenta.

• Optimización de Cartera (Media-CVaR):

  • En un entorno de un solo activo, la DRO exhibe un comportamiento discontinuo de "todo o nada" (saltando de inversión total a cero inversión) a medida que aumenta el radio. En contraste, las políticas de DRRO exhiben un comportamiento no monótono, ajustando gradualmente la exposición para equilibrar el arrepentimiento frente a distribuciones adversas.
  • En entornos multiactivos, la relajación de la DRRO mantiene una exposición positiva a activos de riesgo durante un rango más amplio de radios en comparación con la DRO, que eventualmente se desplaza totalmente hacia el activo libre de riesgo.
  • El análisis teórico sugiere que para radios muy grandes, las políticas óptimas de arrepentimiento convergen a la inversión total en activos de riesgo (debido al alza ilimitado), mientras que la DRO converge al activo libre de riesgo.

Significado y Reivindicaciones
El artículo afirma proporcionar la primera teoría y marco computacional integral para la WDRRO. Sus principales contribuciones son:

1. Perspectiva Teórica: Establecer que en regímenes regulares (pérdidas suaves, ERM único), la robustificación basada en el arrepentimiento es innecesaria ya que la ERM es ya de primer orden óptima. El valor de la WDRRO surge principalmente en regímenes no suaves o de radio grande.
2. Separación de Complejidad: Demostrar que la WDRRO es computacionalmente más difícil que las formulaciones robustas estándar (WDRO, RO, RRO) para pérdidas max-afines, específicamente debido a la maximización externa sobre la decisión de referencia.
3. Algoritmos Prácticos: Proporcionar los primeros algoritmos exactos para la evaluación de la WDRRO y una nueva clase de relajaciones convexas que son tratables, escalables y ofrecen garantías de radio finito.
4. Matiz de Comportamiento: Mostrar que la DRRO puede capturar comportamientos de agresividad o conservadurismo dependientes de la pérdida que la DRO de pérdida en el peor de los casos no detecta.

Los autores concluyen que, si bien la ERM es suficiente en regímenes benignos, la WDRRO es una herramienta necesaria para manejar la especificación incorrecta de la distribución en escenarios complejos, no suaves o de alto riesgo, siempre que se utilicen las relajaciones desarrolladas para gestionar la complejidad computacional.