La curvatura del regret nell’ottimizzazione lineare contestuale

Abstract degli autori

L’apprendimento orientato alle decisioni per l’ottimizzazione lineare è complicato dalla discontinuità dell’ottimizzatore: piccoli errori nella stima dei costi possono lasciare invariata la decisione oppure spostarla su un vertice diverso. Mostriamo che questo comportamento puntuale non liscio diventa localmente quadratico quando si calcola la media sulla distribuzione dei dati e ne ricaviamo la curvatura in forma chiusa: una misura a valori matriciali concentrata sulle pareti del ventaglio normale. Questa misura dipende soltanto dall’insieme ammissibile, mentre la distribuzione dei dati interviene solo come peso. Proponiamo poi un’approssimazione di questa curvatura calcolabile con una sola proiezione sull’insieme ammissibile. Dimostriamo che l’approssimazione converge debolmente alla vera curvatura della popolazione. Presentiamo un’applicazione dei nostri risultati: un metodo di generazione di scenari che tiene conto delle decisioni per l’ottimizzazione lineare del costo atteso. I nostri esperimenti verificano la legge del comportamento quadratico e quella della convergenza debole e mostrano, nell’arbitraggio con batterie, un miglioramento del regret del 30,8% rispetto all’allocazione uniforme.