Wasserstein Distributionally Robust Regret Optimization

Résumé Technique : Optimisation du Regret de Distribution Robustness de type Wasserstein

Énoncé du Problème
La prise de décision en situation d'incertitude repose souvent sur la Minimisation du Risque Empirique (ERM), qui suppose que la distribution empirique représente l'environnement de déploiement. Bien que l'ERM offre de solides garanties hors échantillon sous des hypothèses de lissage et d'i.i.d., elle peut échouer lorsque les distributions d'entraînement et de déploiement divergent. L'Optimisation de Robustesse Distributionnelle (DRO) traite ce problème en minimisant la perte la plus défavorable sur un ensemble d'ambiguïté (typiquement une boule de Wasserstein). Cependant, l'approche de la DRO, focalisée sur la perte la plus défavorable, peut conduire à des politiques excessivement conservatrices, particulièrement dans des contextes présentant un potentiel de gain asymétrique (par exemple, un inventaire à faible coût mais à marge élevée), où la suppression des résultats favorables est sous-optimale.

Pour atténuer ce conservatisme excessif, cet article étudie le Regret de Distribution Robustness ex-ante (DRRO). Contrairement au regret ex-post (qui compare une politique à la meilleure décision pour chaque réalisation spécifique de l'incertitude) ou à la DRO standard (qui minimise la perte la plus défavorable), le DRRO ex-ante minimise le regret le plus défavorable sur un ensemble d'ambiguïté. Le regret est défini comme la différence entre l'espérance de la perte d'une politique et l'espérance de la perte de la politique optimale pour cette distribution spécifique. L'article se concentre sur le Wasserstein DRRO (WDRRO), utilisant des ensembles d'ambiguïté de type-$p$ centrés sur une distribution de référence empirique.

Méthodologie et Cadre Théorique
L'article développe une théorie structurelle et computationnelle du WDRRO, organisée autour d'une dichotomie entre des régimes « réguliers » où l'ERM suffit et des régimes « complexes » où le WDRRO offre des avantages distincts.

1. Théorie de la Sensibilité et Sélection de l'ERM :

   • Optimiseur ERM Unique : Sous des conditions de lissage et de régularité avec un optimiseur ERM unique, l'article prouve que le WDRRO possède une sensibilité de premier ordre nulle par rapport au rayon de Wasserstein $\delta$. Plus précisément, les décisions quasi-optimales du WDRRO satisfont $\theta_\delta = \theta_{ERM} + o(\delta)$. Cela contraste avec la DRO de Wasserstein standard, qui s'éloigne généralement de l'ERM à un ordre de $O(\delta)$.
   • Optimiseur ERM Non-Unique : Lorsque l'ensemble des solutions ERM n'est pas unique, le WDRRO agit comme un régularisateur, sélectionnant les optima de l'ERM qui minimisent l'écart de gradient le plus défavorable par rapport aux autres solutions ERM (un jeu de minimax sur l'écart de gradient).
   • Pertes Quadratiques : Pour les pertes quadratiques strictement convexes avec un ordre de Wasserstein $p \ge 2$, l'article établit que la politique ERM est exactement optimale pour le WDRRO pour tout rayon $\delta$, et non seulement asymptotiquement.

2. Régimes Computationnels et Complexité :

   • L'article identifie que le WDRRO devient computationnellement fragile lorsque les hypothèses échouent (par exemple, pertes non lisses, grands rayons).
   • NP-Dureté : Les auteurs prouvent que l'évaluation du regret WDRRO est NP-difficile même pour des pertes max-affines simples sans termes bilinéaires, en utilisant la distance de Wasserstein de type-1 et une norme de base $\ell_1$. Cette dureté persiste même lorsque le risque Wasserstein interne est tractable, distinguant le WDRRO de la WDRO standard, de l'Optimisation Robuste (RO) et de l'Optimisation de Regret Robuste (RRO), qui restent tractables pour ces mêmes classes de pertes.

3. Solutions Algorithmiques :

   • Algorithmes Exacts : Pour des instances de taille modérée, l'article dérive une formulation non convexe finie du regret en utilisant la dualité de Wasserstein. Cela sert de référence de vérité terrain.
   • Relaxations Convexes : Pour traiter des problèmes plus larges, les auteurs développent des relaxations convexes tractables.
     • Pour les pertes sans termes bilinéaires ($d_k=0$), ils dérivent un programme convexe unique qui borne supérieurement le regret ex-post. Cette relaxation est exacte à $\delta=0$ et pour des rayons supérieurs au diamètre du support, avec un écart d'approximation de $O(\delta)$.
     • Pour les pertes avec termes bilinéaires ($d_k \neq 0$), ils proposent une extension de couverture locale. En couvrant l'espace de décision avec des centres de référence, ils approximent les termes croisés, introduisant un terme d'erreur supplémentaire dépendant du rayon de couverture $\rho$ (spécifiquement $O(\rho \delta)$).

Résultats Clés et Expérimentations
L'article valide sa théorie et ses algorithmes via des expérimentations numériques sur des problèmes de vendeur de journaux (newsvendor) et d'allocation de portefeuille Moyenne-CVaR :

• Problème du Vendeur de Journaux (Newsvendor) :

  • Dans un contexte de faible coût et de marge élevée, la politique DRRO devient plus agressive à mesure que le rayon d'incertitude augmente, alors que la DRO devient plus conservatrice. Cela capture le potentiel de gain (« upside ») que la DRO supprime.
  • Dans un contexte de coût élevé, le DRRO devient plus conservateur, démontrant que la direction de la réponse du DRRO dépend de l'asymétrie des gains.
  • La relaxation convexe proposée suit de près la solution exacte du WDRRO, avec des écarts négligeables dans les quantités commandées et le regret.
  • En termes de calcul, la relaxation proposée passe à l'échelle efficacement pour de grands nombres d'échantillons, tandis qu'une relaxation concurrente (Cho et Yang [14]) devient intractable (NP-difficile) à mesure que la taille de l'échantillon augmente.

• Optimisation de Portefeuille (Moyenne-CVaR) :

  • Dans un cadre à un seul actif, la DRO présente un comportement discontinu de type « tout ou rien » (passant d'un investissement total à un investissement nul) à mesure que le rayon augmente. En revanche, les politiques DRRO présentent un comportement non monotone, ajustant progressivement l'exposition pour équilibrer le regret face aux distributions défavorables.
  • Dans les contextes multi-actifs, la relaxation DRRO maintient une exposition positive aux actifs risqués sur une plage de rayons plus large que la DRO, qui finit par basculer entièrement vers l'actif sans risque.
  • L'analyse théorique suggère que pour de très grands rayons, les politiques optimales au regret convergent vers un investissement total dans les actifs risqués (en raison du gain illimité), tandis que la DRO converge vers l'actif sans risque.

Signification et Revendications
L'article affirme fournir la première théorie complète et le premier cadre computationnel pour le Wasserstein DRRO. Ses principales contributions sont :

1. Insight Théorique : Établir que dans les régimes réguliers (pertes lisses, ERM unique), la robustification basée sur le regret est inutile car l'ERM est déjà optimal au premier ordre. La valeur du WDRRO émerge principalement dans les régimes non lisses ou à grand rayon.
2. Séparation de Complexité : Démontrer que le WDRRO est plus complexe à calculer que les formulations robustes standards (WDRO, RO, RRO) pour les pertes max-affines, spécifiquement à cause de la maximisation extérieure sur la décision de référence.
3. Algorithmes Pratiques : Fournir les premiers algorithmes exacts pour l'évaluation du WDRRO et une nouvelle classe de relaxations convexes qui sont tractables, scalables et offrent des garanties de rayon fini.
4. Nuance Comportementale : Montrer que le DRRO peut capturer des comportements agressifs ou conservateurs dépendants de la perte que la DRO de perte la plus défavorable ne saisit pas, particulièrement dans des environnements de gains asymétriques.

Les auteurs concluent que si l'ERM suffit dans les régimes bénins, le WDRRO est un outil nécessaire pour gérer l'erreur de spécification de distribution dans des scénarios complexes, non lisses ou à enjeux élevés, à condition d'utiliser les relaxations développées pour gérer la complexité computationnelle.