Driving exploration by maximum distribution in gaussian process bandits.

Abstract

Trovare le soluzioni ottime di funzioni stocastiche su domini continui è un problema comune in molte applicazioni reali: allocazione dell'advertising, dynamic pricing, controllo della potenza nelle reti wireless. L'ottimizzazione procede di norma selezionando i punti di input in sequenza e osservando ogni volta un valore rumoroso della funzione.

In questo paper adottiamo l'approccio Multi-Armed Bandit per ottimizzare funzioni stocastiche tenendo sotto controllo il regret, cioè la perdita accumulata durante l'apprendimento. Ci concentriamo sulle funzioni stocastiche smooth: è noto infatti che, se il dominio è continuo e la funzione non soddisfa alcuna condizione di regolarità, ogni algoritmo subisce un regret costante a ogni round.

Il contributo originale del lavoro è una famiglia generale di algoritmi che, sotto l'ipotesi debole che le funzioni stocastiche siano la realizzazione di un Gaussian Process, garantisce un regret dell'ordine di 𝑂(√𝛾𝑇𝑇), dove 𝛾𝑇 è il massimo information gain e 𝑇 l'orizzonte temporale dell'apprendimento.

Progettiamo poi un algoritmo specifico di questa famiglia, DAGP-UCB, che sfrutta la struttura dei GP per scegliere il prossimo arm da giocare in modo più efficace degli algoritmi allo stato dell'arte, accelerando così l'apprendimento. Ne mostriamo le prestazioni superiori sia in scenari sintetici sia applicativi, nel confronto diretto con lo stato dell'arte.