Exploration Monitoring for Online Learning Algorithms

Online learning (OL) is the branch of Machine Learning (ML) that is concerned with the continuous improvement of predictive and decision-making abilities using real-time data. Unlike traditional batch processing, online learning works with streaming data, making it ideal for applications such as dynamic pricing, improving the user experience on news websites, and maximizing the wealth of investments. It is a versatile tool for a variety of tasks, such as click prediction and network routing, and it is characterized by the exploration-exploitation dilemma, balancing the search for optimal choices with the maximization of a given performance measure using known data. This thesis investigates the Multi-Armed Bandit (MAB) problem, a framework for dealing with the exploration-exploitation dilemma. In particular, MAB consists of the modeling of decision-making processes with the goal of maximizing gains over a finite time horizon. Unlike traditional MAB problems, this research focuses on non-stationary environments where change in the reward distribution is possible. The idea for the thesis comes from the necessity to determine if online learning is appropriate for potentially dynamic environments. Indeed, using traditional monitoring methods to check MAB algorithms frequently fails due to their inability to adapt to the unique properties of online learning. Our proposed method combines statistical tests with monitoring techniques to evaluate the quality of exploration within algorithms, ensuring timely adaptation to environmental changes. This methodology helps to make online learning adaptive in non-stationary settings, and it can also provide insights into when an algorithm is not used in the right context. We show, through experimental evidence conducted on synthetic datasets, the necessity of such a methodology and the effectiveness of the proposed solution.

L’Online Learning (OL) è quella branca del Machine Learning (ML) che riguarda il miglioramento continuo delle capacità predittive e decisionali utilizzando dati in tempo reale. L’apprendimento online, a differenza dell’elaborazione batch tradizionale, funziona con i dati in streaming, rendendolo ideale per applicazioni quali prezzi dinamici, miglioramento dell’esperienza dell’utente sui siti Web di notizie e massimizzazione dei ricavi dati da investimenti. È uno strumento versatile per una varietà di compiti, come la previsione dei clic e il routing della rete, ed è caratterizzato dal dilemma esplorazione-sfruttamento, bilanciando la ricerca di scelte ottimali con la massimizzazione di una determinata misura di prestazione utilizzando dati noti. Questa tesi indaga il problema del Multi-Armed Bandit (MAB), un quadro per affrontare il dilemma esplorazione-sfruttamento. In particolare, il MAB consiste nella modellazione dei processi decisionali con l’obiettivo di massimizzare i guadagni su un orizzonte temporale finito. A differenza dei tradizionali problemi MAB, questa ricerca si concentra su ambienti non stazionari in cui è possibile un cambiamento nella distribuzione della ricompensa. L’idea della tesi nasce dalla necessità di determinare se l’apprendimento online è appropriato per ambienti potenzialmente dinamici. Infatti, l’utilizzo dei metodi di monitoraggio tradizionali per verificare gli algoritmi MAB spesso fallisce a causa della loro incapacità di adattarsi alle proprietà uniche dell’apprendimento online. Il metodo proposto combina test statistici con tecniche di monitoraggio per valutare la qualità dell’esplorazione all’interno degli algoritmi, garantendo un adattamento tempestivo ai cambiamenti ambientali. Questa metodologia aiuta a rendere l’apprendimento online adattivo in contesti non stazionari e può anche fornire informazioni su quando un algoritmo non viene utilizzato nel giusto contesto. Mostriamo attraverso prove sperimentali, condotte su set di dati sintetici, la necessità di tale metodologia e l’efficacia della soluzione proposta.