Towards making importance sampling practical

The increasing availability of a large amount of data calls for the need to design techniques able to optimally exploit the information they contain. Reinforcement Learning is a framework based on the idea of learning through data collected from the interaction of an agent with a surrounding environment. Typically, the learning agent tries to learn the optimal policy with the objective of maximizing a utility function. The optimal behavior (also called policy) can be found by means of Policy Search (PS) techniques. Among the different PS methods, Importance Sampling (IS) is a widely used building block for a large variety of off-policy evaluation and learning algorithms. However, empirical and theoretical studies have progressively shown that vanilla IS leads to poor estimations whenever the behavioral and target policies are too dissimilar. This is also due to its heavy-tailed behavior that prevents from defining exponential concentration on the deviation of the estimation from its true mean, thus making the estimation less reliable. In this thesis, we analyze the theoretical properties of the IS estimator by deriving a novel anticoncentration bound that formalizes the intuition behind its undesired behavior. Then, we propose a new class of IS transformations, based on the notion of power mean. This new technique interpolates between the ordinary importance sampling weights and the weights under the on-policy distribution. As far as we know, the designed estimator is the first to achieve, under certain assumptions, two key properties: it displays a subgaussian concentration rate and preserves the differentiability in the target distribution. We also extend the use of the proposed correction to the RL setting. Here, we identify different ways to apply it, according to distinct levels of granularity. A subset of these variants is then analyzed and we are able to provide a new concentration bound for the Per-Decision estimator. Finally, the correction is tested in different settings and compared to stateof- the-art algorithms. We provide numerical simulations on both synthetic examples and contextual bandit settings. The results show that our estimators are competitive and, under certain conditions, outperform existing algorithms. In the RL setting, instead, other experiments are carried out applying the correction to the POIS algorithm.

La sempre maggiore disponibilità di grandi quantità di data aumenta la necessità di avere a disposizione strumenti che permettano di estrarre al meglio l’informazione contenuta in essi. L’apprendimento per rinforzo (RL) è una tecnica che si fonda sull’idea di imparare tramite dati raccolti da ripetute interazioni di un agente con l’ambiente circostante. Tipicamente, l’agente impara una strategia ottimale per eseguire le azioni, dove il concetto di ottimale è legato alla massimizzazione di una funzione di utilità. La strategia ottimale può essere trovata tramite tecniche di Policy Search (PS). Tra i vari metodi di tipo PS, il campionamento per importanza (IS) è una tecnica largamente usata per un vasto insieme di algoritmi che affrontano problemi di valutazione off-policy e apprendimento off-policy. Ciononostante, molti studi hanno dimostrato che la versione standard dell’apprendimento per importanza ha scarsi risultati quando la strategia di comportamento e la strategia obiettivo sono molto diverse tra loro. Ciò è anche dovuto alla proprietà di avere code pesanti, che impediscono di ottenere una concentrazione di tipo esponenziale sulla deviazione del valore stimato rispetto a quello effettivo. Questa tesi si propone di analizzare le proprietà teoriche dello stimatore IS. Durante lo studio, siamo in grado di definire un nuovo limite inferiore per lo stimatore IS formalizzando, dunque, il motivo alla base dei suoi scarsi risultati. In una fase successiva, proponiamo una nuova classe di trasformazioni su IS. Questa nuova tecnica effettua un’interpolazione dei pesi ordinari e dei pesi definiti dalla distribuzione on-policy, tramite un parametro che definisce l’intensità della correzione. In base alle nostre conoscenze, lo stimatore proposto è il primo a godere contemporaneamente di due proprità fondamentali: una concentrazione di tipo subgaussiano e la differenziabilità rispetto ai parametri della strategia obiettivo. La nuova correzione viene poi estesa all’ambito RL, dove possiamo denotare diversi modi di applicazione, a seconda del livello di granularità scelto. Lo studio di un sottoinsieme di queste varianti viene affronato e i risultati ottenuti portano alla derivazione di un nuovo limite superiore di concentrazione per lo stimatore IS Per-Decisione. Infine, la correzione viene testata in contesti differenti e confrontata con gli algoritmi che definiscono lo stato dell’arte. Il lavoro mostra i risultati ottenuti su un esempio costruito ad-hoc e su esperimenti eseguiti nel setting contextual multi-armed bandit. I risultati mostrano che i nostri stimatori sono competitivi e, in alcune circostanze, sono migliori rispetto agli altri algoritmi. Ulteriori esperimenti sono poi effettuati in specifici ambienti appartenenti al setting RL, applicando la nostra correzione all’algoritmo POIS.