ING - Scuola di Ingegneria Industriale e dell'Informazione
4-ott-2018
2017/2018
I vari problemi decisionali sequenziali sono un oggetto di studio dell'intelligenza artificiale. L'apprendimento per rinforzo, è un framework che affronta questi problemi mediante un approccio "trial and error". In questo framework un agente interagisce con un ambiente e raccoglie esperienza da queste interazioni che a sua volta viene utilizzata per trovare la politica ottima da eseguire. Un elemento centrale dell'apprendimento è il segnale di ricompensa (reward) che l'agente riceve dall'ambiente comunicando all'agente se alcuni stati sono desiderati o dovrebbero essere evitati. Si assume che questa ricompensa sia ricevuta immediatamente dopo ogni azione e l'obiettivo dell'agente è quello di massimizzare la ricompensa cumulativa raccolta durante la sua attività nell'ambiente. De nito in questo modo, la funzione reward specifica l'attività che deve essere appresa dall'agente.
Il dilemma exploration vs. exploitation (esplorazione vs. sfruttamento) rimane un argomento principale in reinforcement learning. Il problema consiste nel bilanciare la massimizzazione della ricompensa usando le conoscenze acquisite al momento con l'esplorazione di nuove azioni per migliorare la conoscenza dell'ambiente. Tradizionalmente, l'esplorazione è stata esplicitamente incorporata negli algoritmi scegliendo occasionalmente le azioni in maniera casuale invece di fare afidamento sull'esperienza raccolta; tuttavia rimane una sfida importante nell'apprendimento rinforzato. Strategie di esplorazione comuni, come e-greedy non riescono a condurre esplorazioni estese o profonde. Ciò non solo comporta la necessità di quantità di dati esponenziale per gli algoritmi, ma soprattutto potrebbe causare una convergenza prematura degli algoritmi a una politica subottima o potrebbe impedire del tutto la convergenza. Tradizionalmente, l'apprendimento per rinforzo affronta questi problemi stimando la funzione di valore che quantifica quanto "desiderabili" siano gli stati (o le coppie di stati-azione nel caso di funzione azione-valore). Essendo che gli agenti interagiscono con un ambiente stocastico, la funzione valore è la ricompensa cumulativa attesa a lungo termine.
In questa tesi sviluppiamo un nuovo algoritmo di apprendimento model-free che si basa su lavori recenti che sostengono l'uso delle distribuzioni Q (Q-distributions) per guidare l'esplorazione. Modellando esplicitamente la distribuzione dei valori Q invece di valutare il valore medio, siamo in grado di prendere decisioni più consapevoli e utilizzare queste distribuzioni per guidare l'esplorazione.
Per testare l'algoritmo, iniziamo introducendo il nostro nuovo approccio in domini
finiti semplici, progettati per enfatizzare l'esplorazione, per poi estenderlo a domini continui. Confrontiamo il nostro approccio con algoritmi allo stato dell'arte nei domini Taxi, Loop, Chain, SixArms, RiverSwim e KnightQuest, nonché in vari giochi Atari dall'Arcade Learning Environment.
The various sequential decision making problems are one object of study of Artificial Intelligence. Reinforcement learning addresses these problems in a trial and error way. An agent is required to interact with an environment and collect experience from these interactions which in turn are used to find the optimal policy to pursue. One core element of reinforcement learning is the reward signal that the agent receives from the environment telling the agent if some states are desired or they should be avoided.
This reward is assumed to be immediate after each action and the goal of the agent is to maximize the cumulative reward collected during its activity in the environment. Defined in this way, the reward function specifies the task to be learned by the agent.
The Exploitation- Exploration trade-off remains a main topic in reinforcement learning. The problem consists in balancing reward maximization using the knowledge acquired at the moment with exploring new actions to improve the knowledge of the environment.
Traditionally exploration has been explicitly added to algorithms by occasionally choosing
actions randomly instead of relying on the experience collected, nonetheless it remains
a major challenge in reinforcement learning.
Common exploration strategies, such as
greedy, fail to conduct temporally-extended or deep exploration. This not only causes
exponentially larger data requirements for the algorithms, but most importantly might
cause premature convergence of the algorithms to a suboptimal policy or might prevent
convergence altogether.
Traditionally reinforcement learning faces these problems by estimating the value function which estimates how "good" the states are (or action-states pairs in the case of action-value function). Being that the agents interact with an "uncertain" environment the value-function is the expected cumulative reward collected in the long term.
In this thesis we build on recent work advocating the use of Q-distributions to drive exploration. By explicitly modeling the distribution of the Q-values instead of just estimating the mean we are able to make more informed decisions and use these distributions to drive exploration. Starting from a prior distribution we can update our knowledge with each new sample using a Bayesian approach and we can also use these distributions to quantify the Exploration-Exploitation trade-off.
We start by introducing our new approach in simple finite domains, designed to emphasize exploration, for later extending it to continuous domains. We compare our approach with state of the art algorithms in Taxi , Loop, Chain, SixArms, RiverSwim and KnightQuest domains as well as in various Atari games from the Arcade Learning Environment.