Online Markov Decision Processes configuration with continuous decision space

In this thesis we address the problem of finding the optimal online configuration of episodic finite-horizon Markov Decision Processes when the decision space is a continuous set. In particular, we propose a setting where two agents interact, namely a learning agent (referred to as the configurator) and an agent with a fixed, unknown optimal policy with respect to the original MDP. The configurator can change the transition function in an online manner, in order to minimize her loss values. Although our framework can model several adversarial attacks proposed in the Reinforcement Learning literature, we can also handle more general scenarios, because the configurator's loss and agent's reward functions may be completely unrelated. We develop two different algorithms, namely O-DOSC and O-SOSC, to solve the problem in deterministic settings, where the loss values are fixed, and stochastic settings, where the loss values are sampled from a fixed probability distribution, respectively. Our algorithms are built following the optimism in face of uncertainty principle and, therefore, rely on occupancy measures to explore in an optimistic way the continuous space of transition functions. We achieve constant regret in the deterministic case, matching the lower bound we provide for this problem, while we achieve sublinear regret in the stochastic case. Finally, we empirically validate our results by comparing the proposed algorithms with a baseline, either with discrete and continuous decision spaces.

In questa tesi studiamo il problema di trovare la configurazione ottimale di un Problema Decisionale di Markov (MDP) episodico e con orizzonte temporale finito, quando lo spazio di decisione è un insieme continuo. In particolare, proponiamo una formalizzazione del problema in cui due agenti interagiscono tra loro, ovvero un agente in apprendimento (il configuratore) e un agente con una politica fissata e ottimale rispetto all'MDP originale, sconosciuta al configuratore. Quest'ultimo può modificare in tempo reale la funzione di transizione, in modo da minimizzare i valori delle sue perdite. Sebbene la nostra formalizzazione possa modellare diversi attacchi avversariali presenti nella letteratura dell'Apprendimento per Rinforzo, possiamo in realtà gestire anche scenari più generali, poichè la funzione di perdita del configuratore e quella di ricompensa dell'agente possono essere completamente scorrelate. Abbiamo sviluppato due algoritmi differenti, O-DOSC e O-SOSC, per risolvere il problema rispettivamente sia nel caso deterministico, ossia quando i valori delle perdite del configuratore sono fissati, sia nel caso stocastico, ovvero quando le perdite del configuratore sono campionate da una distribuzione di probabilità fissata. Entrambi i nostri algoritmi sono stati sviluppati seguendo il principio dell'ottimismo di fronte all'incertezza e, pertanto, utilizzano le misure di occupazione per esplorare in maniera ottimistica lo spazio continuo delle funzioni di transizione. Nel caso deterministico, O-DOSC raggiunge un regret costante, che è anche il limite inferiore che abbiamo fornito per il nostro problema, mentre nel caso stocastico O-SOSC raggiunge un regret sublineare. Infine, abbiamo validato in maniera empirica i nostri risultati, confrontando gli algoritmi proposti con una baseline, con spazi di decisione sia discreti che continui.