Non-cooperative configurable Markov decision processes

A Markov Decision Process (MDP) is a mathematical framework for modelling sequential decision making problems. The decision maker is called agent. That interacts with the environment, which represents everything outside the agent. They interacts continuously: the agent selects an action to perform and the environment responds to that action presenting a new situation to the agent. In addition, the environment provides rewards, special numerical values that the agent tries to maximize through the selection of actions. In most applications, the environment is considered a fixed entity out of the agent's control. However, there are many real world problems where we have the possibility to set some environmental parameters. Configurable Markov Decision Processes (Conf-MDPs) are able to model these configurable environments in order to find simultaneously the policy and the environment's configuration that maximize the agent's performance. From an abstract point of view, Conf-MDPs are composed by two cooperative entities: a learning agent, whose aim is to learn the optimal behavior in the environment, and a configurator, which selects environment dynamics that best suit the agent's needs. The question that gives birth to the research topic presented in this thesis is: “what if the agent and the configurator are no longer cooperative?". In that case, the configurator is meant to achieve its own goal possibly different from the one of the agent. In this thesis, we deeply study the non-cooperative interaction between the learning agent and the configurator. We introduce a new extension of Conf-MDPs called Non-Cooperative Configurable Markov Decision Processes (NConf-MDPs) in order to model scenarios where the goal of the configurator does not coincide with that of the agent. Indeed, in some cases it could be even the opposite. Solving a NConf-MDP means finding the configuration that maximizes the configurator's reward function knowing that the agent will act to maximize its own reward function. We propose two algorithms, called Action-feedback Optimistic Configuration Learning (AfOCL) and Reward-feedback Optimistic Configuration Learning (RfOCL), that are able to efficiently solve NConf-MDPs, leveraging the structure of the problem. We provide theoretical performance guarantees of these algorithms showing both theoretically and experimentally that they suffer only bounded regret. Moreover, we present an experimental evaluation on different application domains comparing our algorithms with UCB, that solve NConf-MDPs ignoring the structure of the problem.

L'Apprendimento per Rinforzo rappresenta una delle tre branche principali dell'Apprendimento Automatico, assieme all'Apprendimento Supervisionato e Non Supervisionato. Gli algoritmi di Apprendimento per Rinforzo si basano sull'interazione tra un un decisore, chiamato agente, e l'ambiente. Questa interazione è spesso modellizzata usando i Processi Decisionali di Markov (MDP). L'iterazione tra agente e ambiente avviene in maniera sequenziale: l'agente osserva lo stato dell'ambiente, decide quale azione attuare e l'ambiente risponde fornendo l'osservazione del nuovo stato raggiunto. Inoltre, l'ambiente fornisce all'agente una ricompensa, ovvero una quantità numerica che l'agente cercherà di massimizzare durante la sua interazione con l'ambiente. L'Apprendimento per Rinforzo prende ispirazione dal processo di apprendimento di esseri umani e animali. Infatti, possiamo trovare diverse analogie tra il funzionamento dei MDPs e l'addestramento di un cane: il padrone chiede la zampa e se il cane risponde al comando guadagnerà un biscotto (ricompensa). L'obiettivo implicito del cane è chiaramente massimizzare la quantità di biscotti mangiati. Per raggiungere questo obiettivo il cane dovrà imparare la politica ottima, ovvero alzare la zampa ogni volta che il padrone lo richiede. Nella maggior parte delle applicazioni, l'ambiente è considerato un'entità fissa fuori dal controllo dell'agente. Tuttavia, ci sono molti problemi reali in cui abbiamo la possibilità di modificare alcuni parametri ambientali. Ad esempio, in un'applicazione di guida autonoma, dove lo scopo dell'agente `e imparare a guidare una vettura, potremmo modificare diversi parametri della macchina come la reattività del motore, la stabilità del veicolo o la velocità massima. I Processi Decisionali di Markov Configurabili (Conf-MDPs), sono un'estensione dei MDPs che possono modellizzare gli ambienti configurabili al fine di trovare simultaneamente la politica ottimale dell'agente e la configurazione ambientale che massimizza le sue prestazioni. Da un punto di vista astratto, i Conf-MDP sono composti da due entità cooperative: un agente, il cui scopo è apprendere il comportamento ottimale nell'ambiente, e un configuratore, che seleziona le dinamiche ambientali che meglio si adattano alle esigenze dell'agente. La domanda che ha dato vita al tema di ricerca presentato in questa tesi è: ``cosa potrebbe succedere se l'agente e il configuratore non fossero cooperativi?" In tal caso, il configuratore deve raggiungere un proprio obiettivo potenzialmente diverso da quello dell'agente. Pensiamo, ad esempio, ad un supermercato: un cliente (ovvero l'agente) vuole comprare alcuni prodotti e il suo scopo è acquistare il necessario nel minor tempo possibile; il gestore del supermercato (ovvero il configuratore) deve sistemare i prodotti negli scaffali in modo da indurre il cliente a comprare altro rispetto a quello che aveva pianificato. In questo caso, gli obiettivi dell'agente e del configuratore sono chiaramente diversi: l'agente vuole comprare il necessario nella maniera più efficiente possibile, mentre il configuratore vuole massimizzare i ricavi. In questa tesi, studiamo a fondo l'interazione tra l'agente e un configuratore non-cooperativo. Introduciamo una nuova estensione dei Conf-MDP denominata Processi Decisionali di Markov Configurabili Non-Cooperativi (NConf-MDPs) per descrivere scenari in cui l'obiettivo del configuratore non coincide con quello dell'agente. Risolvere un NConf-MDP significa trovare la configurazione che massimizza la funzione di ricompensa del configuratore sapendo che l'agente agirà per massimizzare la propria funzione di ricompensa. Presentiamo due algoritmi, chiamati Action-feedback Optimistic Configuration Learning} (AfOCL) e Reward-feedback Optimistic Configuration Learning (RfOCL), per risolvere un generico NConf-MDP sfruttando la struttura del problema. Inoltre, forniamo delle garanzie teoriche sulle performance, mostrando sia teoricamente sia sperimentalmente come il rimpianto prodotto dai nostri algoritmi converge a una quantità costante. Infine, presentiamo una valutazione sperimentale su diversi domini applicativi confrontando i nostri algoritmi con UCB, che risolve NConf-MDP ignorando la struttura del problema.