Safe online bid optimization with return-on-investment and budget constraints subject to uncertainty.

Abstract

Nel marketing online l'obiettivo di chi investe è quasi sempre un compromesso tra volumi e redditività. Di solito le aziende lo gestiscono massimizzando i volumi entro una soglia minima di ritorno sull'investimento (ROI). Tecnicamente è un problema di ottimizzazione combinatoria con vincoli di ROI e di budget, da risolvere online: i valori dei parametri sono incerti e vanno stimati mano a mano che arrivano i dati.

Il punto critico è l'incertezza sui parametri dei vincoli: durante l'apprendimento una exploration non controllata può violarli in modo arbitrario, ed è proprio questo uno dei principali ostacoli all'adozione di tecniche automatiche sul campo, perché chi investe considera quel rischio inaccettabile. Perché ci si possa fidare degli strumenti di online learning è quindi essenziale controllare l'exploration, contenere il rischio e garantire la sicurezza per tutta la durata dell'apprendimento.

In questo paper studiamo la natura sia del problema di ottimizzazione sia di quello di apprendimento. Senza incertezza, dimostriamo che il problema non è approssimabile entro alcun fattore a meno che P = NP, e presentiamo un algoritmo in tempo pseudo-polinomiale che ne raggiunge la soluzione ottima. Con l'incertezza, dimostriamo che nessun algoritmo di online learning può violare i vincoli (di ROI o di budget) un numero sublineare di volte garantendo al tempo stesso un pseudo-regret sublineare. Proponiamo quindi GCB, che garantisce regret sublineare al prezzo di un numero potenzialmente lineare di violazioni, e la sua versione sicura GCBsafe, che con alta probabilità mantiene limitato a una costante il numero di violazioni, al prezzo di un pseudo-regret lineare.

Dai due algoritmi precedenti ricaviamo poi GCBsafe(ψ, φ), che con alta probabilità garantisce insieme pseudo-regret sublineare e sicurezza, accettando una tolleranza ψ sul vincolo di ROI e φ su quello di budget. In questo modo il rischio legato alle violazioni si riduce senza rinunciare alla convergenza verso la soluzione ottima.

Infine confrontiamo sperimentalmente i nostri algoritmi sul trade-off tra pseudo-regret e violazioni dei vincoli, in scenari costruiti a partire da dati reali: i risultati mostrano quanto contino nella pratica i vincoli di sicurezza e quanto siano efficaci gli algoritmi proposti.