Breakpoint prediction for the abruptly-changing non-stationary multi-armed bandit problem

Several problems, such as clinical trials and online recommender systems, can be modeled as non-stationary multi-armed bandit (MAB) problems where the distributions of the rewards of the actions change abruptly. Among state-of-the-art policies, actively adaptive policies tackle this problem by coupling policies for the stationary setting with change detection procedures. In this thesis, we propose a novel policy, namely CUSUM-UCB with History (CUH), which takes advantage of the breakpoint prediction capability of change detection procedures. We prove a regret upper bound for an actively adaptive meta-policy which is independent from the stationary subpolicy and the change detection procedure used. Moreover, we prove a regret upper bound for the CUH policy when the maximum amount of history is fixed, which is the first result, up to our knowledge, concerning a MAB policy using breakpoint prediction. Finally, we test CUH against state-of-the-art policies, showing that, when the past history is unbounded, the policy outperforms the state-of-the-art algorithms on the real-world dataset and most of synthetic scenarios.

Molti problemi, come i sistemi di raccomandazione online e i test clinici, possono essere modellizzati come problemi di multi-armed bandit (MAB) in cui le distribuzioni delle ricompense cambiano in certi istanti di tempo sconosciuti all'agente. Tra le politiche stato dell'arte, le politiche di adattamento attivo affrontano il problema proponendo un meta-algoritmo che usa congiuntamente una politica per il caso stazionario e una procedura di rilevamento del cambiamento. In questa tesi, proponiamo una nuova politica, chiamata CUSUM-UCB with History (CUH), che utilizza procedure di rilevamento e stima del preciso istante del cambiamento e riutilizza osservazioni precedenti. Dimostriamo un limite superiore sul regret di una meta-politica di adattamento attivo che è indipendente dalla sotto-politica stazionaria e dalla procedura di rilevamento del cambiamento usati. Inoltre, dimostriamo un limite superiore sul regret ottenuto dalla politica CUH quando viene fissato un massimo numero di osservazioni di storia passata, che è il primo risultato di nostra conoscenza riguardante una politica MAB che stima gli istanti dei cambiamenti. Infine, sperimentiamo la nostra politica CUH comparando i risultati con quelli degli stati dell'arte, mostrando come, quando non viene posto un limite massimo sulle osservazioni di storia passata, la nostra politica ottiene risultati migliori rispetto agli stati dell'arte sia su dataset con dati reali, sia sulla maggioranza dei dataset sintetici.