Stochastic multi-armed bandit with switching costs : an empirical analysis

Software agents implemented to solve Reinforcement Learning tasks usually have to deal with an important strategic dilemma, known in the literature as exploration-exploitation dilemma. More specifically, the dilemma is between the exploitation of the best possible option given the information gathered so far and the exploration of new options to improve the information about the analyzed setting. The Multi-Armed Bandit (MAB) model is the simplest setting in which this dilemma is present. In this problem, an agent must choose, at each time instant, among a finite set of actions, and gains a reward drawn from an unknown distribution corresponding to the chosen action. The agent's goal is to maximize the cumulative reward over a finite time horizon. In this thesis, we aim to analyze a variation of the classical MAB setting, namely MAB with Switching Costs (MAB-SC), that also includes a penalty whenever the agent chooses an action that is different from the one chosen at the previous time instant. Initially, we evaluate the performance of classic MAB algorithms, that do not consider the switching costs, in the setting of our interest. Then, leveraging the results of this initial analysis, we propose new policies that are inspired by those from the state-of-the-art to better suit the MAB-SC setting. We perform a thorough experimental analysis of all of the presented policies which demonstrate the effectiveness of the proposed algorithms in the MAB-SC scenario. Indeed, the empirical analysis shows that most of our novel algorithms outperform those from the state-of-art in the setting with switching costs.

La maggior parte degli agenti programmati per attività di Reinforcement Learning, si trovano a dover affrontare un importante dilemma strategico, noto in letteratura come exploration-exploitation dilemma. Tale dilemma è tra l'utilizzo delle informazioni correnti per attuare la migliore scelta (exploration) e la scelta di opzioni alternative atta ad ampliare le informazioni che l'agente ha allo stato corrente (exploration). Il modello Multi-Armed Bandit è il caso più semplice in cui ci si trova ad affrontare questo dilemma. In tale modello un agente deve scegliere in ogni istante temporale tra un set finito di opzioni, ognuna delle quali fornisce una corrispondente ricompensa stocastica. L'obiettivo dell'agente è quello di massimizzare la ricompensa cumulata durante un orizzonte temporale finito. Lo scopo di questa tesi è quello di analizzare una variante di questo modello che prevede l'inclusione degli switching cost. In tale scenario l'agente viene penalizzato ogni volta che decide di scegliere un'azione diversa da quella scelta all'istante precedente. Inizialmente, prendiamo in considerazione gli algoritmi classici della letteratura Multi-Armed Bandit, che non considerano gli switching cost, e ne analizziamo le prestazioni nel problema di nostro interesse. Sfruttando poi i risultati di questa prima indagine, proponiamo una serie di nuovi algoritmi, ispirati a quelli dello stato dell'arte, atti a migliorane le prestazioni in tale scenario. Il nostro approccio, consiste nell'apportare delle modifiche agli algoritmi esistenti per far si che cambino la loro decisione il meno possibile da un istante temporale all'altro. Al fine di testarne le performance, abbiamo eseguito un'accurata analisi sperimentale di tutti gli algoritmi presentati che ci fornisce risultati estremamente soddisfacenti. Le performance empiriche di quasi tutti i nuovi algoritmi, infatti, risultano essere migliori di quelli già esistenti in letteratura.