Exploiting maximum distribution to drive exploration in Gaussian process bandits

The problem of finding optimal solutions of stochastic functions over continuous domains is common in several real-world applications, such as, e.g., advertisement allocation, dynamic pricing, and power control in wireless networks. The optimization process is customarily performed by selecting input points sequentially and receiving a noisy observation from the function. In this thesis, we resort to the Multi-Armed Bandit approach, aiming at optimizing stochastic functions when keeping at a pace the regret, i.e. the loss incurred during the learning process. In particular, we focus on smooth stochastic functions, as it is known that any algorithm suffers from a constant per-round regret when the domain is continuous, and the function does not satisfy any kind of regularity. Our main original contribution is the provision of a general family of algorithms, which, under the mild assumption that the stochastic functions are a realization of a Gaussian Process, provides a regret of the order of the square of the product of γT and T, being γT the maximum information gain and T the time used for the learning process. Furthermore, we design a specific algorithm of our family, called DAGP-UCB, which exploits the structure of Gaussian Process (GP) to select the next arm to pull more effectively than the previous algorithms available in the state of the art, thus speeding up the learning process. In particular, we show the superior performance of DAGP-UCB in both synthetic and applicative settings, comparing it with the state-of-the-art algorithms.

Il problema di trovare soluzioni ottimali per funzioni stocastiche su domini continuiè comune a molte applicazioni, come nell’allocazione di ad pubblicitari, pricing dinamico e per il controllo dell’alimentazione nelle reti wireless. Il processo di ottimizzazione viene solitamente eseguito selezionando in sequenza diversi punti di input (detti arm) e ricevendo un’osservazione rumorosa della funzione stessa. In questa tesi si ricorre all’approccio MultiArmed Bandit, con l’obiettivo di ottimizzare il processo di apprendimento di funzioni stocastiche minimizzando il Regret (ciè la perdita subita durante il processo di apprendimento). In particolare, ci concentriamo sulle funzioni stocastiche che presentano caratteristiche di continuità e regolarità, in quantoè noto che qualsiasi algoritmo soffre di un regret costante perround quando il dominioè continuo e la funzione non soddisfa alcun tipo di regolarità. Il nostro principale contributoè la definizione di una famiglia generale di algoritmi, i quali assumendo che le funzioni stocastiche siano una realizzazione di un Processo Gaussiano, forniscano un regret dell’ordine della radice di γT per T, dove γTè il massimo Information Gain e T il tempo utilizzato per il processo di apprendimento. Inoltre, abbiamo definito un algoritmo specifico della nostra famiglia, chiamato DAGP-UCB, che sfrutta la struttura dei GP per selezionare l’arm successivo, in questo modo l’algoritmoè capace di imparare più efficacemente degli algoritmi disponibili allo stato dell’arte, velocizzando cosi il processo di apprendimento. In particolare, mostriamo che le prestazioni di DAGP-UCB sono migliori sia negli esperimenti sintetici che in quelli eseguiti su uno scenario applicativo, confrontandoli con gli algoritmi dello stato dell’arte.