Multi-armed bandits in dynamic environments and heavy-tailed rewards

The Multi-Armed Bandit (MAB) problem is a theoretical framework that models a broad range of sequential decision-making problems. Over the last two decades, the MAB framework has experienced a rapid growth in interest from both the theoretical research community and practitioners: on one hand, there are several technical challenges posed by proving theoretical guarantees on algorithms; on the other hand, MAB algorithms have been used in relevant real-world applications such as dynamic pricing and digital advertising. In this work, we examine some of the most significant streams of research in MABs, primarily from a theoretical perspective. In particular, we aim to relax some of the core assumptions of the MAB framework, making it more suited for real-world scenarios, and provide algorithms with provable theoretical guarantees. We mainly focus on the regret minimization problem, where the decision-maker observes a realization of the reward of an action after having chosen it, and aims at maximizing the overall total reward at the end. We aim at bridging the MAB problem with Markov Decision Process (MDP) problem, and to provide MAB-style algorithm with provable theoretical guarantees in the latter. Such settings do not allow for trivial characterizations of the optimal policy, allowing past actions to affect the present. The largest literature on regret minimization in MABs deals with stochastic realizations that come from fixed and well-behaved (e.g., bounded support or sub-Gaussian) probability distributions. In this thesis, we address the heavy-tailed bandit problem, where assumptions on the reward-generating distributions are reduced to the bare minimum, and the variance may be infinite.

Il problema del Multi-Armed Bandit (MAB) rappresenta un quadro teorico che modella un’ampia varietà di problemi di decisione sequenziale. Nel corso degli ultimi due decenni, il modello MAB ha suscitato un crescente interesse sia nella comunità di ricerca teorica sia tra i professionisti: da un lato, vi sono numerose sfide tecniche legate alla dimostrazione di garanzie teoriche sugli algoritmi; dall’altro, gli algoritmi MAB sono stati applicati con successo in importanti contesti reali, come la definizione dinamica dei prezzi e la pubblicità digitale. In questo lavoro, esaminiamo alcuni dei filoni di ricerca più rilevanti nell’ambito dei MAB, principalmente da una prospettiva teorica. In particolare, ci proponiamo di rilassare alcune delle assunzioni fondamentali del modello, rendendolo più adeguato a scenari reali, e di fornire algoritmi dotati di garanzie teoriche dimostrabili. Ci concentriamo soprattutto sul problema della minimizzazione del \textit{regret}, in cui il decisore osserva la realizzazione della ricompensa di un’azione dopo averla scelta e mira a massimizzare il totale delle ricompense ottenute al termine dell’orizzonte temporale. Il nostro obiettivo è creare un collegamento tra il problema MAB e quello dei Markov Decision Process (MDP), fornendo algoritmi in stile MAB che mantengano garanzie teoriche anche in quest’ultimo contesto. Tali scenari non consentono, in generale, delle caratterizzazioni banali della politica ottimale, poiché le azioni passate influenzano quelle future. La maggior parte della letteratura sulla minimizzazione del regret nei MAB considera realizzazioni stocastiche che provengono da distribuzioni di probabilità fisse e molto regolari (ad esempio distribuzioni con supporto limitato o sub-Gaussiane). In questa tesi, affrontiamo il problema degli heavy-tailed bandits, in cui le assunzioni sulle distribuzioni che generano le ricompense sono ridotte al minimo indispensabile e la varianza di quest'ultime può essere infinita.