Best model selection via stochastic rising bandits

Stochastic Rising Bandits is a setting in which the values of the expected rewards of the available options increase every time they are selected. This framework models a wide range of scenarios in which the available options are learning entities whose per- formance improves over time. In this Thesis, we focus on the Best Arm Identification (BAI) problem for the stochastic rested rising bandits. In this scenario, we are asked, given a fixed budget of rounds, to provide a recommendation about the best option at the end of the selection process. We propose two algorithms to tackle the above-mentioned setting, namely R-UCBE, which resorts to a UCB-like approach, and R-SR, which employs a successive reject procedure. We show that they provide guarantees on the probability of properly identifying the optimal option at the end of the learning process. Finally, we numerically validate the proposed algorithms in synthetic and realistic environments and compare them with the currently available BAI strategies.

Il setting Stochastic Rising Bandits è tale per cui i valori dei reward attesi delle opzioni disponibili aumentano ogni volta che vengono selezionate. Questo framework modella un’ampia gamma di scenari in cui le opzioni disponibili sono entità di apprendimento le cui prestazioni migliorano nel tempo. In questa tesi, ci concentriamo sul problema dell’identificazione dell’opzione (i.e., arm) migliore (BAI) per gli stochastic rested rising bandits. In questo scenario, ci viene chiesto, dato un budget fisso di round, di fornire una raccomandazione sulla migliore opzione alla fine del processo di selezione. Proponiamo due algoritmi per affrontare il suddetto scenario, ovvero R-UCBE, che ricorre a un approccio di tipo UCB, e R-SR, che impiega una procedura di scarti sequenziali. Dimostriamo che essi forniscono garanzie sulla probabilità di identificare correttamente l’opzione ottimale alla fine del processo di apprendimento. Infine, convalidiamo numericamente gli algoritmi proposti in ambienti sintetici e realistici e li confrontiamo con le strategie BAI attualmente disponibili.