Wasserstein Distributionally Robust Regret Optimization

Sintesi Tecnica: Ottimizzazione del Regret Distribuito Robusto di Wasserstein

Enunciato del Problema
Il processo decisionale in condizioni di incertezza si basa spesso sulla Minimizzazione del Rischio Empirico (ERM), la quale assume che la distribuzione empirica rappresenti l'ambiente di implementazione. Sebbene l'ERM offra forti garanzie fuori campione sotto ipotesi di regolarità e i.i.d., può fallire quando le distribuzioni di addestramento e di implementazione divergono. L'Ottimizzazione Distribuita Robusta (DRO) affronta questo problema minimizzando la perdita nel caso peggiore su un insieme di ambiguità (tipicamente una palla di Wasserstein). Tuttavia, l'approccio della DRO, focalizzandosi sulla perdita nel caso peggiore, può portare a politiche eccessivamente conservative, specialmente in contesti con potenziale di guadagno asimmetrico (ad esempio, inventario a basso costo e alto margine), dove sopprimere gli esiti favorevoli è subottimale.

Per mitigare tale eccessiva conservativismo, questo articolo studia l'Ottimizzazione del Regret Distribuito Robusto ex-ante (DRRO). A differenza del regret ex-post (che confronta una politica con la migliore decisione per ogni specifica realizzazione dell'incertezza) o della standard DRO (che minimizza la perdita nel caso peggiore), la DRRO ex-ante minimizza il regret nel caso peggiore su un insieme di ambiguità. Il regret è definito come la differenza tra la perdita attesa di una politica e la perdita attesa della politica ottimale per quella specifica distribuzione. L'articolo si concentra sulla WDRRO di Wasserstein, utilizzando insiemi di ambiguità di tipo-$p$ centrati su una distribuzione di riferimento empirica.

Metodologia e Quadro Teorico
L'articolo sviluppa una teoria strutturale e computazionale della WDRRO, organizzata attorno a una dicotomia tra regimi "regolari" dove l'ERM è sufficiente e regimi "complessi" dove la WDRRO offre vantaggi distinti.

1. Teoria della Sensibilità e Selezione dell'ERM:

   • Ottimizzatore ERM Unico: Sotto condizioni di regolarità e regolarità con un ottimizzatore ERM unico, l'articolo dimostra che la WDRRO ha una sensibilità del primo ordine nulla rispetto al raggio di Wasserstein $\delta$. Nello specifico, le decisioni quasi-ottimali della WDRRO soddisfano $\theta_\delta = \theta_{ERM} + o(\delta)$. Ciò contrasta con la standard DRO di Wasserstein, che tipicamente si sposta lontano dall'ERM di ordine $O(\delta)$.
   • Ottimizzatore ERM Non Unico: Quando l'insieme delle soluzioni ERM non è unico, la WDRRO agisce come un regolarizzatore, selezionando gli ottimi ERM che minimizzano la discrepanza del gradiente nel caso peggiore rispetto ad altre soluzioni ERM (un gioco minimax di discrepanza del gradiente).
   • Perdite Quadratiche: Per perdite quadratiche strettamente convesse con ordine di Wasserstein $p \ge 2$, l'articolo stabilisce che la politica ERM è esattamente WDRRO-ottimale per qualsiasi raggio $\delta$, non solo asintoticamente.

2. Regimi Computazionali e Difficoltà:

   • L'articolo identifica che la WDRRO diventa computazionalmente fragile quando le assunzioni falliscono (ad esempio, perdite non regolari, raggi elevati).
   • NP-Hardness: Gli autori dimostrano che valutare il regret della WDRRO è NP-difficile anche per semplici perdite max-affine senza termini bilineari, utilizzando la distanza di Wasserstein di tipo-1 e una norma di base $\ell_1$. Questa difficoltà persiste anche quando il rischio di Wasserstein interno è trattabile, distinguendo la WDRRO dalla standard WDRO, dalla Robust Optimization (RO) e dalla Robust Regret Optimization (RRO), che rimangono trattabili per le stesse classi di perdita.

3. Soluzioni Algoritmiche:

   • Algoritmi Esatti: Per istanze di medie dimensioni, l'articolo deriva una formulazione non convessa finita del regret utilizzando la dualità di Wasserstein. Questa funge da benchmark di verità fondamentale.
   • Relassazioni Convesse: Per gestire problemi più grandi, gli autori sviluppano rilassazioni convesse trattabili.
     • Per perdite senza termini bilineari ($d_k=0$), derivano un singolo programma convesso che pone un limite superiore al regret ex-post. Questa rilassazione è esatta per $\delta=0$ e per raggi superiori al diametro del supporto, con un gap di approssimazione di $O(\delta)$.
     • Per perdite con termini bilineari ($d_k \neq 0$), propongono un'estensione a copertura locale (local-cover extension). Coprendo lo spazio decisionale con centri di riferimento, approssimano i termini incrociati, introducendo un termine di errore aggiuntivo dipendente dal raggio di copertura $\rho$ (specificamente $O(\rho \delta)$).

Risultati Chiave ed Esperimenti
L'articolo valida la sua teoria e i suoi algoritmi attraverso esperimenti numerici sui problemi del venditore (newsvendor) e sull'allocazione di portafoglio Mean-CVaR:

• Problema del Venditore (Newsvendor):

  • In un contesto a basso costo e alto margine, la politica DRRO diventa più aggressiva all'aumentare del raggio di incertezza, mentre la DRO diventa più conservativa. Ciò cattura il potenziale di "guadagno" (upside) che la DRO sopprime.
  • In un contesto ad alto costo, la DRRO diventa più conservativa, dimostrando che la direzione della risposta della DRRO dipende dall'asimmetria del payoff.
  • La rilassazione convessa proposta segue da vicino la soluzione esatta della WDRRO, con gap trascurabili nelle quantità ordinate e nel regret.
  • In termini di computazione, la rilassazione proposta scala efficientemente a grandi dimensioni di campioni, mentre una rilassazione concorrente (Cho e Yang [14]) diventa intrattabile (NP-hard) all'aumentare della dimensione del campione.

• Ottimizzazione di Portafoglio (Mean-CVaR):

  • In un contesto a singolo asset, la DRO mostra un comportamento discontinuo "tutto o niente" (passando da un investimento totale a zero investimento) all'aumentare del raggio. Al contrario, le politiche DRRO mostrano un comportamento non monotono, regolando gradualmente l'esposizione per bilanciare il regret rispetto alle distribuzioni avverse.
  • In contesti multi-asset, la rilassazione DRRO mantiene un'esposizione positiva verso gli asset rischiosi su un intervallo di raggi più ampio rispetto alla DRO, che alla fine si sposta interamente verso l'asset privo di rischio.
  • L'analisi teorica suggerisce che per raggi molto grandi, le politiche ottime per il regret convergono verso l'investimento totale in asset rischiosi (a causa del guadagno illimitato), mentre la DRO converge verso l'asset privo di rischio.

Significato e Rivendicazioni
L'articolo sostiene di fornire la prima teoria e il primo quadro computazionale completo per la WDRRO. I suoi principali contributi sono:

1. Approfondimento Teorico: Stabilire che in regimi regolari (perdite regolari, ERM unico), la robustificazione basata sul regret è superflua poiché l'ERM è già ottimale al primo ordine. Il valore della WDRRO emerge principalmente in regimi non regolari o con raggi elevati.
2. Separazione della Complessità: Dimostrare che la WDRRO è computazionalmente più difficile delle standard formulazioni robuste (WDRO, RO, RRO) per perdite max-affine, specificamente a causa della massimizzazione esterna sulla decisione di riferimento.
3. Algoritmi Pratici: Fornire i primi algoritmi esatti per la valutazione della WDRRO e una nuova classe di rilassazioni convesse che sono trattabili, scalabili e offrono garanzie a raggio finito.
4. Sfumatura Comportamentale: Mostrare come la DRRO possa catturare comportamenti aggressivi o conservativi dipendenti dalla perdita che la DRO basata sul caso peggiore della perdita manca.

Gli autori concludono che, sebbene l'ERM sia sufficiente in regimi benigni, la WDRRO è uno strumento necessario per gestire la misspecificazione distributiva in scenari complessi, non regolari o ad alta posta in gioco, a patto di utilizzare le rilassazioni sviluppate per gestire la complessità computazionale.