Towards fully-adaptive regret minimization in heavy-tailed bandits

The stochastic multi-armed bandit problem is well understood in settings where the reward distributions are subgaussian or have bounded support. In this thesis, we revisit the classic regret minimization problem in the stochastic bandit setting where the arm distributions are allowed to be heavy-tailed. We work under the weaker assumption that the distributions have finite moments of maximum order 1+epsilon, with epsilon in (0,1], which are uniformly bounded by a constant u. These heavy-tailed distributions naturally arise in common real-world contexts where uncertainty has a significant impact, including finance, telecommunications and network traffic. Thus, it is important to understand and develop a general theory and efficient algorithms, both computationally and statistically, that have wider applicability and are tailored to handle such practical scenarios effectively. Any approach that requires prior knowledge on the distribution parameters is not applicable in these cases, since epsilon and u are not known in real-world, and not even easily quantifiable. In this work, we move towards the adaptive heavy-tailed bandit setting, where no information is provided to the agent regarding the moments of the distribution, not even which of them are finite. Besides proving that no algorithm, without any additional assumption, can match the performances of the non-adaptive setting, the main novelty we introduce in the thesis is AdaR-UCB. It is an algorithm based on the optimism in the face of uncertainty principle that is capable of being fully adaptive with respect to the two parameters epsilon and u. Under a specific but not restrictive distributional assumption, namely the truncated non-positivity, it is able to achieve performances comparable to the optimal approaches knowing the aforementioned quantities. To the best of our knowledge, this is the first regret minimization strategy in the stochastic adaptive heavy-tailed bandit setting that does not require any prior knowledge on epsilon nor u, but still achieves optimality, with a regret upper bound matching the well known lower bound for the standard non-adaptive setting. Finally, we evaluate numerically and compare our algorithm on a range of heavy-tailed bandit instances, noting that it outperforms several state-of-the-art baselines.

Il modello Multi-Armed Bandit stocastico è stato ampiamente studiato in ambienti dove le ricompense sono variabili aleatorie subgaussiane o con supporto finito. In questa tesi, rivisitiamo il classico problema di minimizzazione del regret nel contesto stocastico dove le distribuzioni delle azioni sono a coda pesante. Lavoriamo sotto l'assunzione che abbiano momento finito di massimo ordine 1+epsilon, con epsilon in (0,1], maggiorato uniformemente dalla costante u. Queste distribuzioni con code pesanti emergono naturalmente in contesti del mondo reale, quali la finanza, le telecomunicazioni e le reti di traffico. È quindi importante sviluppare una teoria generale e algoritmi efficienti che abbiano un'applicabilità più ampia e gestiscano efficacemente questi scenari pratici. Qualsiasi approccio che richieda una conoscenza a priori sui parametri delle distribuzioni non è applicabile in questi casi, poiché epsilon e u non sono noti né quantificabili nel mondo reale. In questo lavoro, ci orientiamo verso lo studio dei modelli stocastici bandit in un contesto adattivo, in cui non viene fornita all'agente alcuna informazione sui momenti delle distribuzioni, nemmeno su quali siano finiti. Oltre a dimostrare che nessun algoritmo, senza alcuna assunzione aggiuntiva, è in grado di eguagliare le prestazioni degli approcci non adattivi, la principale novità introdotta nella tesi è AdaR-UCB. Si tratta di un algoritmo basato sul principio dell'ottimismo di fronte all'incertezza, che è in grado di essere completamente adattivo rispetto ai due parametri epsilon e u. Sotto una specifica ma non restrittiva assunzione di non-positività troncata, è in grado di raggiungere risultati paragonabili agli approcci ottimali che conoscono le suddette quantità. Al meglio delle nostre conoscenze, questa è la prima strategia di minimizzazione del regret, nell'ambito del modello bandit stocastico adattativo a code pesanti, che non richiede alcuna conoscenza a priori né di epsilon né di u, ma raggiunge comunque l'ottimalità, con un limite superiore sul regret che combacia con il ben noto limite inferiore per il problema standard non adattativo. Infine, valutiamo numericamente e confrontiamo il nostro algoritmo su una serie di istanze a coda pesante, notando che empiricamente ha performance migliori dello stato dell'arte in letteratura.