Wasserstein Distributionally Robust Regret Optimization

Technische Samenvatting: Wasserstein Distributionele Robuuste Regret Optimalisatie

Probleemstelling
Besluitvorming onder onzekerheid steunt vaak op Empirical Risk Minimization (ERM), wat ervan uitgaat dat de empirische distributie de implementatieomgeving representeert. Hoewel ERM sterke out-of-sample garanties biedt onder aannames van gladheid en i.i.d., kan het falen wanneer de trainings- en implementatiedistributies uiteenlopen. Distributionele Robuuste Optimalisatie (DRO) pakt dit aan door te minimaliseren over een ambiguïteitsset (typisch een Wasserstein-bal), gericht op de worst-case verwachte loss. Echter, de adversariële focus van DRO op de worst-case loss kan leiden tot overmatig conservatieve beleidsregels, met name in scenario's met een asymmetrisch opwaarts potentieel (bijv. lage kosten, hoge marges bij voorraadbeheer), waarbij het onderdrukken van gunstige uitkomsten suboptimaal is.

Om deze overmatige conservatisme te mitigeren, bestudeert dit artikel ex-ante Distributionele Robuuste Regret Optimalisatie (DRRO). In tegenstelling tot ex-post regret (dat een beleid vergelijkt met de beste beslissing voor elke specifieke realisatie van onzekerheid) of standaard DRO (dat de worst-case loss minimaliseert), minimaliseert ex-ante DRRO de worst-case regret over een ambiguïteitsset. Regret wordt gedefinieerd als het verschil tussen de verwachte loss van een beleid en de verwachte loss van het optimale beleid voor die specifieke distributie. Het artikel richt zich op Wasserstein DRRO (WDRRO), gebruikmakend van type-$p$ Wasserstein-ambiguïteitssets gecentreerd rond een empirische referentiedistributie.

Methodologie en Theoretisch Kader
Het artikel ontwikkelt een structurele en computationele theorie van WDRRO, georganiseerd rond een dichotomie tussen "reguliere" regimes waar ERM volstaat en "complexe" regimes waar WDRRO duidelijke voordelen biedt.

1. Sensitiviteitstheorie en ERM Selectie:

   • Unieke ERM Optimizer: Onder voorwaarden van gladheid en regulariteit met een unieke ERM-optimizer, bewijst het artikel dat WDRRO een nul eerste-orde sensitiviteit heeft ten opzichte van de Wasserstein-straal $\delta$. Specifiek voldoet een bijna-optimale WDRRO-beslissing aan $\theta_\delta = \theta_{ERM} + o(\delta)$. Dit staat in contrast met standaard Wasserstein DRO, dat doorgaans van orde $O(\delta)$ afwijkt van ERM.
   • Niet-unieke ERM Optimizer: Wanneer de ERM-oplossingsverzameling niet uniek is, fungeert WDRRO als een regularisator die ERM-optima selecteert die de worst-case gradiënt-discrepantie tegenover andere ERM-oplossingen minimaliseren (een minimax gradiënt-discrepantie spel).
   • Kwadratische Losses: Voor strikt convexe kwadratische losses met Wasserstein-orde $p \ge 2$, stelt het artikel vast dat het ERM-beleid exact WDRRO-optimaal is voor elke straal $\delta$, niet alleen asymptotisch.

2. Computationele Regimes en Hardheid:

   • Het artikel identificeert dat WDRRO computationeel fragiel wordt wanneer aannames niet standhouden (bijv. niet-gladde losses, grote radii).
   • NP-Hardheid: De auteurs bewijzen dat het evalueren van de WDRRO-regret NP-hard is, zelfs voor eenvoudige max-affine losses zonder bilaterale termen, gebruikmakend van type-1 Wasserstein-afstand en een $\ell_1$ grondnorm. Deze hardheid blijft bestaan zelfs wanneer de innerlijke Wasserstein-risico tractabel is, wat WDRRO onderscheidt van standaard WDRO, Robust Optimization (RO) en Robust Regret Optimization (RRO), die voor dezelfde loss-klassen tractabel blijven.

3. Algoritmische Oplossingen:

   • Exacte Algoritmen: Voor middelgrote instanties leidt het artikel een eindige niet-convexe formulering van de regret af met behulp van Wasserstein-dualiteit. Dit dient als een ground-truth benchmark.
   • Convexe Relaxaties: Om grotere problemen aan te pakken, ontwikkelen de auteurs tractabele convexe relaxaties.
     • Voor losses zonder bilaterale termen ($d_k=0$), leiden zij een enkel convex programma af dat de ex-post regret begrenst. Deze relaxatie is exact bij $\delta=0$ en bij radii groter dan de diameter van de support, met een benaderingsfout van $O(\delta)$.
     • Voor losses met bilaterale termen ($d_k \neq 0$), stellen zij een local-cover extensie voor. Door de beslissingsruimte te dekken met benchmark-centra, benaderen zij de kruistermen, wat een extra foutterm introduceert die afhankelijk is van de covering-straal $\rho$ (specifiek $O(\rho \delta)$).

Belangrijkste Resultaten en Experimenten
Het artikel valideert de theorie en algoritmen via numerieke experimenten op nieuwe vendor-problemen en mean-CVaR portfolio allocatie:

• Newsvendor Probleem:

  • In een setting met lage kosten en hoge marges wordt het DRRO-beleid agressiever naarmate de onzekerheidsstraal toeneemt, terwijl DRO conservatiever wordt. Dit vangt het "opwaartse" potentieel dat DRO onderdrukt.
  • In een setting met hoge kosten wordt DRRO juist conservatiever, wat aantoont dat de richting van de DRRO-respons afhangt van de asymmetrie van de payoff.
  • De voorgestelde convexe relaxatie volgt de exacte WDRRO-oplossing nauwgezet, met verwaarloosbare verschillen in hoeveelheden en regret.
  • Wat betreft computationele aspecten schaalt de voorgestelde relaxatie efficiënt naar grote steekproefgroottes, terwijl een concurrerende relaxatie (Cho en Yang [14]) onberekenbaar (NP-hard) wordt naarmate de steekproefgrootte toeneemt.

• Portfolio Optimalisatie (Mean-CVaR):

  • In een setting met één asset vertoont DRO een discontinue "alles-of-niets" gedraging (sprong van volledige investering naar nul investering) naarmate de straal toeneemt. In contrast hiermee vertonen DRRO-beleidsregels niet-monotoon gedrag, waarbij ze geleidelijk de blootstelling aanpassen om de regret te balanceren tegen ongunstige distributies.
  • In settings met meerdere assets behoudt de DRRO-relaxatie een positieve blootstelling aan risicovolle activa over een breder bereik van radii vergeleken met DRO, dat uiteindelijk volledig verschuift naar de risicovrije asset.
  • Theoretische analyse suggereert dat voor zeer grote radii, regret-optimale beleidsregels convergeren naar volledige investering in risicovolle activa (vanwege de onbegrensde opwaartse potentie), terwijl DRO convergeert naar de risicovrije asset.

Betekenis en Claims
Het artikel claimt de eerste uitgebreide theorie en computationele framework voor Wasserstein DRRO te bieden. De primaire bijdragen zijn:

1. Theoretisch Inzicht: Vaststellen dat in reguliere regimes (gladde losses, unieke ERM), regret-gebaseerde robustificatie niet nodig is omdat ERM al eerste-orde optimaal is. De waarde van WDRRO komt primair naar voren in niet-gladde of regimes met grote radii.
2. Complexiteitsseparatie: Aantonen dat WDRRO computationeel moeilijker is dan standaard robuuste formuleringen (WDRO, RO, RRO) voor max-affine losses, specifiek door de uiterlijke maximalisatie over de benchmark-beslissing.
3. Praktische Algoritmen: Het bieden van de eerste exacte algoritmen voor WDRRO-evaluatie en een nieuwe klasse van convexe relaxaties die tractabel, schaalbaar en voorzien van finite-radius garanties zijn.
4. Gedragsnuance: Laten zien dat DRRO zowel agressieve als conservatieve gedragingen kan vangen die afhankelijk zijn van de loss, wat de worst-case loss van DRO mist, met name in asymmetrische payoff-omgevingen.

De auteurs concluderen dat hoewel ERM volstaat in bendige regimes, WDRRO een noodzakelijk instrument is voor het omgaan met distributionele mis-specificatie in complexe, niet-gladde of scenario's met hoge inzet, mits men de ontwikkelde relaxaties gebruikt om de computationele complexiteit te beheersen.