Multi-armed bandit with persistent reward

Tasks that requires decision-making under uncertainty are usually linked with the well-known exploration-exploitation dilemma, i.e., the search for a balance between exploiting the best possible option given the current knowledge or exploring new alternatives for potential future benefit. The Multi-Armed Bandit (MAB) framework offers an easy to use and theoretically grounded option to solve this dilemma, and has been applied successfully in a wide range of real-world problems. In this setting, an agent must choose, at each time instant, among a finite set of actions, and gains an instantaneous reward drawn from an unknown distribution corresponding to the chosen action. However, a number of real-world scenarios are not cased in the standard MAB formulation, due to the fact that the reward corresponding to an action is gained over multiple time instants following the action. To handle such a scenario, we formalize a variation of the MAB problem, namely MAB with Persistent Reward (MAB-PR), we developed algorithms capable to tackle the addressed problem, and analyzed them from a theoretical perspective. Finally, we performed a thorough experimental analysis that demonstrate the effectiveness of the novel algorithms both on synthetically generated data and real-world data, coming from two applications of recommender systems and dynamic pricing.

I problemi di scelta sequenziale in condizioni di incertezza sono spesso legati ad un importante dilemma strategico noto in letteratura con il nome di exploration/exploitation dilemma. Ciò consiste nel trovare il giusto compromesso tra scegliere opzioni promettenti sulla base della conoscenza acquisita sino ad ora (exploitation), o esplorare nuove opzioni alternative allo scopo di ottenere un possibile beneficio futuro (exploration). Il modello Multi-Armed Bandit (MAB) esemplifica e affronta questo dilemma in modo semplice ma con una solida base teorica, infatti, è stato applicato con successo ad una vasta gamma di problemi reali. Nel modello MAB, un agente, ad ogni istante temporale, deve selezionare un'azione da un insieme di alternative valide. La scelta di un'azione fa sì che l'agente guadagni istantaneamente una ricompensa estratta da una distribuzione sconosciuta corrispondente all'azione scelta. Tuttavia, un grande numero di scenari reali non sono rappresentati dal tale modello poiché, nelle loro natura, la ricompensa derivante dall'azione è percepita dall'agente in modo distribuito nel tempo successivo all'azione stessa. Al fine di gestire tali scenari, abbiamo formalizzato una variante del modello MAB chiamata MAB con Persistenza nella Ricompensa (MAB-PR), sviluppato algoritmi specifici per tale modello e li abbiamo analizzati da un punto di vista teorico. Infine, abbiamo condotto un'analisi sperimentale che dimostra l'efficacia dei nuovi algoritmi introdotti sia in configurazioni con dati generati sinteticamente, sia in configurazioni con dati reali derivanti da due applicazioni di sistemi di raccomandazione e dynamic pricing.