Multi-armed stochastic bandits: an optimistic approach in sequential learning​

In spite of the rich research on multi-armed bandits, only a few articles in the literature have underlined the importance of the choice, in terms of performance, of the principle ¿optimism in face of uncertainty¿. In this thesis we want to outline more strategies that follow this concept, translating a problem of a stochastic and sequential nature, to an optimistic optimization structure. Particular attention is given not only to the search space under the exploration-exploitation dilemma, but also to how the strategies can be reformulated in the absence of information on the smoothness of the mean-payoff function. We also present a recent result of non-existence of an adaptive strategy for the semi-metric, leaving open the problem of other consistent and suitable assumptions that might help to structure adaptive algorithms in the branch of active-sequential learning.

Nonostante la ricca ricerca riguardo i multi-armed bandits, solo in pochi articoli si è sottolineata l'importanza della scelta, in termini di prestazione, del principio ¿optimism in face of uncertainty¿. In questa tesi si vogliono delineare più strategie che seguono tale concetto, traducendo un problema di natura stocastica e di tipo sequenziale, ad una struttura di ottimizzazione ottimista. Particolare attenzione è prestata non solo allo spazio di osservazione, ma anche a come le strategie possano essere riformulate in assenza di informazione sulla regolarità della funzione di guadagno. Presentiamo inoltre un recente risultato di non esistenza di una strategia adattiva per la semi-metrica, lasciando aperto il problema di quali altre assunzioni, consistenti ed opportune alla realtà, possano aiutare a strutturare algoritmi adattivi nella branca dell'active-sequential learning.