Reinforcement Learning using the Gym Retro platform

Reinforcement Learning using the Gym Retro platform Aprendizaje por refuerzo en la plataforma Gym Retro Universidad Complutense de Madrid Facultad de Inform´ atica Trabajo de Fin de Grado del Doble Grado en Ingenier´ıa Inform´atica y Matem´aticas Curso 2021/22 Autores: Mar´ ıa Arranz Lobo, Manuel Llorca Ron, Manuel Ortega Salvador Directores: Bel´ en D´ ıaz Agudo, Antonio Alejandro S´ anchez Ruiz-Granados Abstract The Gym Retro framework enables implementation of reinforcement learning in classic video games. In this project we will explore the creation of automatic playing agents that learn to play some of these games using Deep Reinforcement Learning techniques. We will also explore techniques that allow us to intuitively explain the decisions taken by the trained models. All of this is done by first giving an overview of the theory behind the algorithms and tools and then applying them in increasingly complex environments. We start with the CartPole problem, a very basic environment typically used as an introduction to reinforcement learning, and we use both a symbolic and a subsymbolic approach. Once we consider that we have solved that problem, we repeat the process with the Space Invaders Atari environment, which is a much more complex task. Finally, we try to use all the previous knowledge in order to train an AI that plays Space Invaders in its NES version, which is a slightly newer console than the Atari 2600 and should be a small step up. For each of the AIs that learn through vision, we test our RISE-based explainability solution. Keywords Artificial Intelligence, Reinforcement Learning, Deep Learning, DQN, Gym Retro, XAI, Explainability, RISE I Resumen La plataforma Gym Retro facilita la aplicaci´on de t´ecnicas de aprendizaje por refuerzo en videojuegos cl´asicos. En este trabajo exploraremos la creaci´on de jugadores autom´aticos que aprendan a jugar a alguno de estos juegos usando t´ecnicas de aprendizaje profundo por refuerzo. Tambi´en investigaremos t´ecnicas que permitan explicar de forma intuitiva las decisiones que toman los modelos entrenados. Todo esto se realizar´a de la siguiente manera: primero comenzaremos por resumir la teor´ıa detr´as de los algoritmos y herramientas a usar, y luego la aplicaremos en entornos incrementalmente complejos. Empezaremos por el problema del CartPole, un entorno muy b´asico usado t´ıpicamente como introducci´on al aprendizaje por refuerzo. Usaremos una aproximaci´on tanto simb´olica como subsimb´olica. Una vez consideremos que hemos resuelto ese problema, repetiremos el proceso con el entorno Space Invaders de Atari, una tarea mucho m´as compleja. Por ´ultimo, intentamos usar todo el conocimiento previo para entrenar una IA que juega a Space Invaders en su versi´on de NES, que es una consola ligeramente posterior a la Atari 2600 y representa una peque˜na subida en complejidad. Para cada una de las IAs que aprenden por visi´on, probaremos nuestra soluci´on de explicabilidad basada en RISE. Palabras clave Inteligencia Artificial, Aprendizaje por refuerzo, Aprendizaje profundo, DQN, Gym Retro, XAI, Explicabilidad, RISE III Contents 1 Introduction 1 1.1 Objectives.................................... 4 1.2 Workplan .................................... 4 1.3 MemoryStructure ............................... 6 1.4 Repository.................................... 6 2 Deep Reinforcement Learning: theory and technologies 7 2.1 Reinforcement Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1.1 Q-Learning ............................... 9 2.2 DeepLearning.................................. 11 2.3 Deep Reinforcement Learning . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.3.1 DeepQ-Learning ............................ 13 2.4 Explainable Reinforcement Learning . . . . . . . . . . . . . . . . . . . . . 14 2.5 Gym....................................... 15 2.6 GymRetro ................................... 16 2.7 Tensorforce ................................... 17 2.8 Colab ...................................... 18 3 CartPole environment: an initial approach 19 3.1 CartPoleenvironment ............................. 19 3.2 DefaultCartPole ................................ 20 3.2.1 Default CartPole with Q-Learning . . . . . . . . . . . . . . . . . . . 21 3.2.2 Default CartPole with DQN . . . . . . . . . . . . . . . . . . . . . . 22 3.3 CartPolewithvision .............................. 24 3.3.1 CartPole with vision applying DQN . . . . . . . . . . . . . . . . . . 25 3.4 Conclusions ................................... 26 4 Video game environments 28 4.1 AtariEnvironment ............................... 28 4.2 AtariwithRAMvalues............................. 29 4.2.1 Atari RAM with DQN . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.3 Atari with screen input . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.3.1 Atari vision with DQN . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.4 NESEnvironment................................ 34 4.5 NESwithRAMvalues ............................. 34 4.5.1 NESRAMwithDQN ......................... 35 4.6 NESwithscreeninput ............................. 37 4.6.1 NES vision with DQN . . . . . . . . . . . . . . . . . . . . . . . . . 37 V CONTENTS 4.7 Video game environments conclusion . . . . . . . . . . . . . . . . . . . . . 38 5 Explainable Deep Reinforcement Learning 40 5.1 Saliencymaps.................................. 40 5.2 RISE....................................... 41 5.3 RISE for Deep Q-Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 5.3.1 Explaining CartPole with vision . . . . . . . . . . . . . . . . . . . . 43 5.3.2 Explaining video game environents . . . . . . . . . . . . . . . . . . 44 5.3.3 Conclusions ............................... 45 6 Conclusions 46 6.1 Futurework................................... 48 Appendices 49 A Personal contributions to the project 50 A.1 Mar´ıaArranzLobo............................... 50 A.2 ManuelLlorcaRon............................... 52 A.3 ManuelOrtegaSalvador ............................ 54 Bibliography 56 VI List of Figures 1.1 Symbolic AI for playing Space Invaders .................... 2 1.2 Subsymbolic AI for playing Space Invaders .................. 2 1.3 Example of XAI applied to an image classifier [7].............. 3 1.4 Increasing complexity of environments .................... 5 2.1 Agent-Environment cycle in reinforcement learning [11]........... 8 2.2 Example of the Frozen Lake environment with Q-values for each tile [13]. 11 2.3 Deep neural network with 3 hidden layers [15]................ 12 2.4 Comparison between Q-Learning and Deep Q-Learning [19]......... 14 3.1 Visualization of the CartPole environment .................. 19 3.2 Default CartPole Q-Learning: Average reward for every 2000 episodes. . . 22 3.3 Default CartPole Q-Learning: Average duration for every 2000 episodes. . 22 3.4 Our neural network with two hidden dense layers of 64 neurons [29]. . . . 23 3.5 Default CartPole DQN: Average reward for every 100 episodes. ....... 23 3.6 Default CartPole DQN: Average duration for every 100 episodes. ...... 23 3.7 Example of extracted screen .......................... 24 3.8 Vision CartPole DQN: Average reward for every 100 episodes. ....... 26 3.9 Vision CartPole DQN: Average duration for every 100 episodes. ...... 26 4.1 Atari Space Invaders game ........................... 29 4.2 Atari Space Invaders DQN with RAM: Average reward for every 100 episodes. 31 4.3 Atari Space Invaders DQN with RAM: Average duration for every 100 episodes. ..................................... 31 4.4 Atari Space Invaders DQN with screen vision: Average reward for every 10 episodes. ..................................... 33 4.5 Atari Space Invaders DQN with screen vision: Average duration for every 10 episodes. ................................... 33 4.6 NES Space Invaders game ........................... 34 4.7 NES Space Invaders DQN with RAM: Average reward for every 20 episodes. 36 4.8 NES Space Invaders DQN with RAM: Average duration for every 20 episodes. 36 4.9 NES Space Invaders DQN with screen vision: Timesteps for every episode. 36 4.10 NES Space Invaders DQN with screen vision: Reward for every episode. . . 38 4.11 NES Space Invaders DQN with screen vision: Duration for every episode. . 38 4.12 NES Space Invaders DQN with screen vision: Timesteps for every episode. 39 5.1 Overview of the RISE explanation process [34]................ 41 5.2 CartPole: examples of saliency maps where the agent’s focus is on key parts of the image ................................... 43 VII CHAPTER 1. INTRODUCTION However, deep reinforcement learning algorithms, which combine reinforcement rearning techniques with the power of neural networks, face some challenges that make it harder to generate human interpretable explanations. One of the reasons is that, in contrast with classic problems of supervised or unsupervised learning problems, in which the set of data is static, in reinforcement learning the environment is dynamic because the agent’s actions affect and modify the environment (e.g the agent did a series of actions A,B,C to avoid a certain penalty or in order to receive a reward or achieve the final goal). It also involves a large amount of actions, often taken in real time, that are constructed after training over really long periods of time. Another big problem for constructing explanations is that in reinforcement learning algorithms we do not have prior training data, since in this case the agent is the one who finds this data over time by exploring the environment. 1.1 Objectives Now we will state some of the objectives that we want to pursue. •O1: The main goal of this work is to better understand the current state of deep reinforcement learning and whether it is really usable both in computer performance needs and in ease of use. To achieve this several smaller objectives are set: -O1.1: Gain a comprehensive knowledge about Deep Reinforcement Learning and the Deep Q-Learning algorithm. -O1.2: Implement the algorithm in several increasingly complex environments, determining the difficulties that each environment adds to the problem at hand. -O1.3: Analyze the obtained results to determine the applicability of this technology in a practical setting or if it still needs some refinement to be able to obtain useful results without needing massive computing power. •O2: In addition to this, we will attempt to apply explainability techniques to the black box system that neural networks are. It seems like this is still a very unexplored field, considering how recent deep reinforcement learning algorithms are and how hard is to develop reasonable XAI techniques for both reinforcement learning and neural networks. Thus, any development on this field will be considered very positive. 1.2 Workplan In order to achieve these objectives, we will train Deep Q-Network (DQN) [8] agents in increasingly complex environments (fig. 1.4) and compare the obtained results. The steps will then be the following: 1. CartPole environment: First some preliminary tests will be conducted on the CartPole environment. It is a very basic test environment included in the OpenAI Gym [9] library which will allow some familiarization with the techniques applied and with the tools used in the whole process. We expect to obtain good results 4 CHAPTER 1. INTRODUCTION Figure 1.4: Increasing complexity of environments without a big computational time, since input data will not be of great dimensions. Two different approaches will be used to tackle the problem. •CartPole with default input values: The version of the CartPole environment that comes bundled in Gym provides four input values that describe the current status of the state. This simplicity makes it perfect as a starting point to get everything setup properly and obtain a working agent that solves this problem. The simplicity of this task will also allow us to test the performance of Deep Q-Learning compared to the original Q-Learning, and decide whether it makes sense to apply such an advanced technique for this low-complexity example. •CartPole using screens as input: The default version of CartPole allows rendering of the current situation of the environment, but does not explicitly provide the RGB values of the generated screen. We will attempt to generate our own information of the visualization of the environment and train an agent that learns from these screens, not from the symbolic states. This will then be a perfect opportunity to learn about the creation of a custom environment in Tensorforce [10]. We will also attempt to adapt XAI techniques that are usually applied to image classifiers to try to understand how the agent makes its decision. 2. Atari environment: These will be the first real use-case tests. Atari 2600 is the main console tested in the revolutionary DeepMind [1] papers. We will train an AI that plays a certain Atari 2600 game using the Deep Q-Learning algorithm, and grasp the true potential of the technique and understand the areas in which it can excel. Once again, two approaches will be taken. •Atari 2600 using RAM as input: The original Atari 2600 console had a RAM of 128 bytes of size. Thus, using it as the “states” from which the DQN agent trains seems like a reasonable approach computationally speaking, and will be an interesting test to distinguish if the agent is able to learn to play reasonably well using RAM values or it would be more worth it to use the vision approach, despite being more power demanding. •Atari 2600 using screen pixels as input: This approach would imply that the agent is really learning only from what a human could possibly see, since the possibly hidden information inside the Atari’s RAM is no longer available to the agent. This is the way the Deep Q-Learning agent is trained in the original DeepMind paper, according to which it surpasses the performance of all previous algorithms that tried to tackle this problem. Therefore, we expect 5 CHAPTER 1. INTRODUCTION to obtain positive results in this area, with the key factors being the time and power cost of the training phase, considering the typical screen resolution of an Atari game is of 210 x 160 colored pixels. This phase will also be essential in deciding whether the XAI techniques generated for the vision CartPole environment are easily scalable and can be generally applied to agents that learn from images. 3. NES Environment: This stage starts making use of the full GymRetro [5] platform potential, as we will try to repeat the results obtained in the Atari stage in a posterior console with more complex environments and states. We will once again train DQN agents using both the NES’ RAM (2KB) and game screens (256x240 colored pixels) as input. The comparison will then be direct with the previous stage, and will generate discussion on the real scalability of the DQN algorithm. 1.3 Memory Structure In Chapter 2 we describe the overall tools and techniques used in the realization of this project. We start by introducing the concept of Reinforcement Learning, giving a definition for the Markov Decision Process. Then we cover the algorithmic methods that we will study to solve the problem at hand: Q-Learning and Deep Q-Learning. Also the problem of explainability is discussed. In addition, an overview of technologies and frameworks such as Gym, Tensorforce and Colab is given. In Chapter 3 we use the techniques described in Chapter 2 in a classical reinforcement learning environment: the Cartpole environment. Various approaches are implemented and tested generating several agents that are then evaluated to benchmark performance. In Chapter 4 we first describe the Atari and NES video game environments, both in RAM and screen versions, in which we apply the DQN algorithm. We then benchmark the agents generated for each environment against each other to conclude what is their practical value in more complex settings. In Chapter 5 we introduce importance (or saliency) maps as a way of interpreting the behaviour of neural networks. Then, the RISE method for the generation of such maps is implemented and tested against the agent developed in Chapter 3. Finally, in Chapter 6 we summarize the conclusions and results of this work. This is done by additionally reviewing each work objective and reflecting on to which extent have been achieved. 1.4 Repository The notebooks that contain the code that we have executed, as well as the trained models can be found in the following GitHub repository: https://github.com/tfg-gym-retro/Implementation-TFG 6 Chapter 2 Deep Reinforcement Learning: theory and technologies In this chapter, various tools and techniques that will be used throughout our work will be presented. The reader will be able to know more about Reinforcement Learning, and why it makes sense to combine it with Deep Learning. The advantages and weaknesses of each of them will be discussed and their theory explained before starting the practical experiments. Then we will provide the software and technologies used throughout our testing. 2.1 Reinforcement Learning Humans are used to the concept of learning as a way to acquire new abilities. Sometimes they learn because someone has told them the actions that they should attempt to mimic, the steps that must be done to achieve their goals. Other times learning is made from their own experiences and mistakes. When they are faced with a situation that has many possible courses of action, they try to choose the one that will get them closer to their final objective. Of course, which choice is the optimal one, if there is any, is not always immediately obvious, and much trial and error has to be done. Reinforcement Learning [11] has more resemblances with this latter approach. The idea behind it is that the agent should map different states to the action that is most beneficial in each of them. At first, randomness plays a great role, since the agent has no idea on what the results of any of their actions could be. But once it starts taking action, it slowly turns that lack of knowledge into information. It is important to note here that a balance needs to be struck between using past knowledge and exploring new actions in each state. It obviously would make no sense to always do a random action when the whole purpose of the algorithms is to learn from their past choices, but it would be equally wrong to assume that just because an action yields a positive result there does not exist another action that could perform even better. The agent also needs a way to understand whether the action it has taken was a positive, negative, or neutral choice. For this purpose, the agent receives a virtual reward after making each move that allows it to learn. This is comparable to the “experience” that one would obtain in the real world. 7 CHAPTER 2. DEEP REINFORCEMENT LEARNING: THEORY AND TECHNOLOGIES Figure 2.1: Agent-Environment cycle in reinforcement learning [11] From a technical point of view, the environment in which the agent acts is modeled as a Markov Decision Process in the following way (fig. 2.1): •We define Sas a set that contains every possible state of our environment. We can also define S(t) as the representation of the state that the agent receives at the timestep tof the execution of the algorithm. •We may also define A(St) as the set of possible actions that the agent can perform in the state St. Note how it depends on the timestep tsince not all actions may be available in all states. •After the agent performs the action At∈A(St) given the state St, the environment reacts and advances to the state St+1, providing the agent with a numerical reward Rt+1 ∈R. Informally speaking, the agent will try to maximize the total reward it receives on the long run. The probability that the action Atin a state swill lead to another state s′is the transition probability Pss′=P(St+1 =s′|St=s). •The expected return is what will actually be tried to maximize on each run. For episodic tasks, an easy definition of the expected return function Gtthat needs to be maximized is Gt= T−t X k=1 γk−1Rt+k where T is the timestep in which we arrive to a terminal state and γis the discount rate. Note how this correlates to the idea of maximizing the long-term rewards. Another important element is defining a representation of the behaviour of the agent, in the sense of giving a reason to picking an action over other choices. This is what the policy of the agent is for, mapping a certain state to the probability of taking each action. This is denoted by πt(a|s) and represents the probability of choosing the action a=At in the state s=St. Each reinforcement learning method then defines how this policy evolves over time. In the end, the main goal of the agent in a Markov Decision Process is to find a good policy πthat manages to maximize some cumulative function of the rewards defined earlier. In addition to the policy, we can also have what is called the value function, which is the long-term value of a state or an action. We can have a state-value function to represent the expected return value starting from a state sand then taking a policy π, 8 CHAPTER 2. DEEP REINFORCEMENT LEARNING: THEORY AND TECHNOLOGIES and can be expressed as vπ(s) = Eπ[Gt|St=s] We can also take into account the action, and now we have an action-value function, which is the expected return starting from a state sand taking an action a, and then following the policy π qπ(s, a) = Eπ[Gt|St=s, At=a] Both trying to find an optimal policy or trying to maximize the state-value function or the action-value function can lead to the agent learning an optimal behaviour. Thus, depending on which one they try to optimize, the field of Reinforcement Learning algorithms can be split into two sections: Policy-Based Algorithms and Value-Based Algorithms. We must also talk about the idea of breaking the training into episodes, which are subsequences of learning that make sense as a whole. This means, an episode spans from the moment in which the agent starts acting in an initial state of the environment until it reaches a terminal state in which it can act no more. In a videogame, this is very easily understood, since one can consider an episode to last from the moment the videogame starts up to a game over or a victory. Thus, the training process typically covers a big number of episodes. Although there are situations in Reinforcement Learning in which the concept of episode does not make sense, since the interest is in continuous learning and there are no terminal states, we will focus on reinforcement learning by episodes. Now let’s get some more insight on one of the most simple yet effective reinforcement learning algorithms, Q-Learning. 2.1.1 Q-Learning Among all the reinforcement learning algorithms, Q-Learning [12] is one of the most basic, since it doesn’t require of a model of the environment. The way it works is simple: the agent tries an action in a specific state, and evaluates its consequences depending on the reward or penalty and its estimate of the value of the next state. Q-Learning can also be viewed as a method of dynamic programming, because it uses previously learned states, in the sense that they have been already explored, to consider future decisions. All these values are stored in a table called Q-table, which contains the maximum future expected reward for each action taken from each state. The Q-values of the Q-table are updated using the following equation: Qnew(st, at) = Q(st, at) + α·rt+γ·max aQ(st+1, a)−Q(st, at) We define the parameters in the following way: •αis the learning rate (0 ≤α≤1). It determines how much of the new information is actually retained in contraposition to keeping the old knowledge. A factor of 0 would mean that the agent learns absolutely nothing and will only use prior knowledge. Meanwhile, a factor of 1 would make the agent only remember its most recent results. •γis called the discount rate (0 ≤γ≤1). This factor establishes the importance of rewards in the long-term. If it has a value of 0, it will make the agent only 9 CHAPTER 2. DEEP REINFORCEMENT LEARNING: THEORY AND TECHNOLOGIES care about instant rewards, which undermines the purpose of maximizing the longterm benefits. On the other hand, a value of 1 will make the agent permanently worried about an infinitely “far away” reward, which also usually leads to undesired behavior. •rtis the reward for the action attaken from the state st. The Q values can be initialized to 0 or to a random value, and are updated through the training. Since in Q-Learning at first the agent knows nothing about the environment and the problem that it’s in, first the action-state space must be explored to determine the effects of taking different actions from multiple states, so the agent can learn what actions generate a more desirable result. This the called the exploration/exploitation dilemma. One of the simplest ways of dealing with this is the ϵ-greedy approach. A new parameter ϵwill be introduced, which indicates the probability of taking a random action instead of taking the one with the best Q-value from that state. The idea is that we start with a high ϵ allowing the agent to explore, and as the training progresses, we decay that value so in the end we take a greedier approach by prioritizing the actions that the agent has discovered to be of higher value. To get a better understanding of how the Q-Learning algorithm works, we present a simple problem in which we can easily apply this reinforcement learning method. The Frozen Lake [13] problem consists in a 4x4 grid, in which some tiles are walkable, while others are holes, meaning the agent falls into the lake. There are two versions of this environment: slippery, in which the movement of the agent is uncertain because there’s a chance of sliding and moving in a direction different from the desired one; and non-slippery, which removes that chance of slipping and moving on a random direction. The objective is to get from the starting tile to the goal tile, so the agent is rewarded for finding a valid path. The only actions we can take for each state is to move up, down, left or right. So our Q-table will be initialized as a 16x4 table of zeroes (16 states and 4 actions per state, see fig. 2.2 for a graphic representation). As we explained before, we can initially start with a high epsilon value (like 70% for example), so we can explore the environment at first, and we progressively lower it so at the end we take a greedier approach to get better results. The Q-table will be updated through the whole training using the formula presented earlier. We use the non-slippery version for the example as it’s easier to understand. As our Q-table starts with all zeroes and the only way to get a reward is to get to the goal, at the beginning all actions take the same priority, so we can take an ϵ-greedy approach, allowing the agent to explore at the beginning until we reach the goal a number of times. This way the Q-table can be properly updated since we would have achieved a reward higher than 0, and as the training goes on we start giving more priority to the action with the higher Q-value in each state. This way, the first time we get to the goal after taking the action atfrom the state st, the Q-value Q(st, at) will be updated with the formula we presented earlier, since we have gotten a reward higher than 0. Then, if we get to that state stfrom another state sr, the Q-value Q(sr, ar) will be updated since one of the Q-values of the state stis also higher than 0, and so on. As we keep the training going episode after episode, the Q-values of 10 CHAPTER 2. DEEP REINFORCEMENT LEARNING: THEORY AND TECHNOLOGIES Figure 2.2: Example of the Frozen Lake environment with Q-values for each tile [13] more states start getting values higher than 0 in the case that they offer a path to reach the goal, as if we were building a path from the goal to the starting state. This way, towards the end of the training we start prioritizing the best Q-value for the state that we are in instead of continuing to explore alternative actions. After a certain number of episodes the agent will be able to take a path that will always reach the goal without failure as a result of the learning process. 2.2 Deep Learning While it is hard to precisely define what Deep Learning [14] is, it is widely accepted as a kind of machine learning that utilizes artificial neural networks in order to achieve its goals. The term deep makes reference to the use of multiple layers in the neural network, which allows learning representations of data with various levels of abstraction. Neural networks consist of an input layer, followed by one or more hidden layers consisting of a certain number of neurons, and then a final output layer of neurons (fig. 2.3). They are able to learn representations automatically from raw inputs, recovering the compositional hierarchy of the input, i.e., high-level features are often composed of low-level ones. The main advantage of using neural networks is that since they can learn the true often non-linear complex relationships between inputs and outputs, they can reach fairly accurate expressions of their relationship and therefore predict the output on inputs that were not in the training space. Each perceptron recieves the values xifrom the ones on the previous layer, and multiplies each one of them by a weight value wiassigned for each of the xivalues. Then, we add a bias b, so we can establish how high the weighted sum must be for the perceptron to be “meaningfully active”. In summary, for each perceptron in the layer we’ll have this value: z=Xxiwi+b 11 CHAPTER 2. DEEP REINFORCEMENT LEARNING: THEORY AND TECHNOLOGIES Figure 2.3: Deep neural network with 3 hidden layers [15] Lastly, we will apply a non linear transformation, called activation function, to our z value, so we can decide whether the neuron activates or not by mapping the z values to an interval, like [0,1], or simply to get a new representation of the values from the previous layer. Some examples of commonly used activation functions are the logistic (or Sigmoid) function, tanh, or the rectified linear unit (ReLU). σ(z) = 1 1 + e−zLogistic function ϕ(z) = ez−e−z ez+e−zTanh function ReLU(z) = max(0, z) ReLU function Some examples of deep neural networks are the multilayer perceptron (MLP), which maps some input values to some other output values by applying a function that is basically broken into smaller functions at each one of the perceptron layers. Another common type is the convolutional neural network (CNN), which is a network with convolutional layers, pooling layers and fully connected layers, designed to proccess data with multiple arrays, like colour images, audio spectogram and video. One important thing to take into account when training a neural network with a dataset is that it can produce a wrong prediction or an expected output that differs from the one produced by the machine learning model. That’s why, in order to quantify this error or difference in outputs, we introduce a loss function[16]. There are many examples of loss functions, and each of them work better in different specific tasks. For example the Mean Squared Error (MSE) loss is used in regression tasks, which is the mean of the squared differences of the expected and the target outputs; or the Binary Crossentropy (BCE) loss is used for binary classification. Loss functions are used to calculate gradients, which are later used to update the weights of the neural network in order to optimize it by reducing the loss. Gradients are as the multi-variable derivative of the loss function with respect to all the network parameters, that’s why they indicate the “direction” in which the loss function increases faster. A 12 CHAPTER 2. DEEP REINFORCEMENT LEARNING: THEORY AND TECHNOLOGIES way to solve this is with the Gradient Descent algorithm[17], which updates each of the weights by subtracting the vector of gradients multiplied by the learning rate, and this process is repeated through the training until the loss is minimized, even though it can end up converging to a local minima. Another optimization algorithm designed for training deep neural networks is the Adam [18] algorithm. It uses the squared gradients to scale the learning rate, while also taking advantage of momentum by using moving average of gradient instead of just using the gradient itself. Since Adam is an adaptive learning rate method, it computes individual learning rates for different parameters, using first and second moments of gradient to adapt the learning rate for each weight of the neural network. The first and second moments of gradient refer to the expected value of gradient to the power of 1 and 2, respectively. 2.3 Deep Reinforcement Learning Reinforcement Learning[4] can be combined with deep learning [14], making use of neural networks to approximate any of the different values of reinforcement learning that we explained earlier, like the Q values in Q-Learning, the policy, the transition function or the reward function. Now, in the same way that we did on the previous section about reinforcement learning, we will introduce a version of the Q-Learning algorithm that makes use of deep learning, called Deep Q-Learning. 2.3.1 Deep Q-Learning Deep Q-Learning (or DQN, from Deep Q-Network)[8] permits the application of Qlearning to big problems in which the state space or the number of different actions that the agent can take is way too large to fit reasonably in a Q-table without needing excessive quantities of memory or computing power. The solution that Deep Q-Learning proposes is to approximate the Q-values by means of a machine learning model such as a neural network. This allows for reduced computation times and no need for disproportionate space requirements, significantly reducing the size of the Q-table. We can see the comparison between standard Q-learning and deep Q-learning in figure 2.4. An improvement from the standard Q-Learning algorithm is that the DQN produces at once the Q values for each of the possible actions, instead of having to execute the network individually for each action. Approximating the action-value function in reinforcement learning algorithms can lead to instability, as we need the training data to be independent and evenly distributed. Researchers at DeepMind found two ways of solving this problem. First, instead of using a sequence of tuples of the agent’s past experiences, for the DQN they kept a replay memory, used to store a history of tuples of state, action, reward and other important information. In each iteration of the DQN a random batch of previous experiences is taken from the replay memory, this way avoiding “harmful” correlations in the data when updating the neural network. This technique is called experience replay. 13 CHAPTER 3. CARTPOLE ENVIRONMENT: AN INITIAL APPROACH In the environment, we can apply a fixed force to the cart to make it move in either direction in order to try to balance the pole. Each episode is considered to be finished when the pole deviates more than 12 degrees from being vertical, or when the cart moves more than 2.4 units away from the starting point (this would happen when the center of the cart reaches the edge of the display). As the agent observes the current state of the environment and chooses an action, the environment transitions to a new state, and also returns a reward that indicates the consequences of the action. This reward will be a constant value of 1 for every timestep that the agent is able to keep the pole from falling, meaning that better performing agents episodes will run for a larger amount of timesteps. Now we will present two versions of training the CartPole problem, which differ in the data that’s used to train the agent. In the default one we present a symbolic approach, using only values of the environment such as the pole angle and the position of the cart, while in the vision approach we look directly at the whole screen to get information about the state that we’re in. All of the experiments with this environment were done in a computer with 16 GB of RAM and an Intel(R) Core(TM) i7-8750H @ 2.20GHz CPU. 3.2 Default CartPole In our first approach to the CartPole problem, we will use real numeric values obtained directly from the environment in order to train the agent. These are the following: •Cart position: Represents the horizontal location of the cart in the screen. It has a minimum value of -4.8 and a maximum value of 4.8, where a value of 0 would mean that the cart is in the center of the screen. As stated earlier, an episode would be considered to be finished if this value is smaller than -2.4 or bigger than 2.4, since this would mean that the cart has left the visible area of the screen. •Cart velocity: Represents the speed at which the cart is moving. This value can be any number. If it is a negative value, it means that the cart is moving left, while if it is a positive value, the cart moves right. •Pole angle: Represents the angle of the pole with respect to a completely vertical position, which would be 0º. As before, a negative value would mean that the pole leans left, while a positive value expresses that the pole is leaning to the right. While it can take any value between -24ºand 24º, taking a value smaller than -12º or bigger than 12ºwould end the episode, as this would imply that “the pole has fallen”. •Pole angular velocity: Represents the speed at which the pole is leaning to either side. It can take any numeric value. If it is a negative one, the pole will tend to incline to the left. Otherwise, it will tend to incline to the right. It is important to observe that at the start of each episode each one of these items is assigned a uniformly random value in (-0.05, 0.05). That way, the agent needs to learn to control the cart in various similar initial situations instead of just learning the best strategy for a default initial state. Episodes will also terminate after 500 timesteps, since it is considered that the agent has been able to keep the pole from falling and just executing more timesteps would not add any more valuable information. 20 CHAPTER 3. CARTPOLE ENVIRONMENT: AN INITIAL APPROACH Parameter Value Learning rate (α) 0.1 Discount rate (γ) 0.95 Exploration (ϵ) 1 Exploration decay 0.99995 Table 3.1: Default CartPole Q-Learning: Parameters Now that we understand how the default CartPole environment works, it is time to train an agent and see how well it learns. We follow two different approaches: first we use the Q-Learning algorithm, and then we are going to try using a DQN. 3.2.1 Default CartPole with Q-Learning Since the Cartpole environment isn’t a very complex problem, our first attempt at training an agent will be by using one of the most simple reinforcement learning algorithms, QLearning. As we explained, our only possible actions are moving right or moving left, and the only variables of the environment are four: cart position, cart velocity, pole angle and pole angular velocity; so the dimensions of the Q-table shouldn’t be too complex. In this case we create our Q-table and update it manually through the training using the formula we presented earlier, as well as update other variables needed for the training. As all variables are continuous, we must discretize the states so we can fit different ranges of those values into different sets, making it so that the resulting Q-table is finite. We discretize the cart position and velocity to 30 values, and the pole angle and velocity to 50. This way our Q-table will be composed of 30 ×30 ×50 ×50 ×2 = 4500000 different states. We manually construct the Q-table having the states represented by its properties (cart position, cart velocity, pole angle and velocity), that is, the state space is represented by a 4-dimensional matrix and therefore, the Q-table is a 5-dimensional one, initializing each pair of action and state to a random value between 0 and 1. The parameters of the training are presented in table 3.1. We first set the agent to train for 10000 episodes, but seeing how the training ended in around 5 seconds, we allowed the agent to go for 500000 episodes in an attempt to maybe obtain better results and because the duration of the training wouldn’t be as long as how it was going to be with other algorithms. Through the training we stored the reward obtained and the duration of every episode, so at the end we can plot these values in a graph and check the evolution of the training. For the sake of simplifying the visualization of the result, we calculated the average reward and duration for every 2000 episodes, and in fig. 3.2 and fig. 3.3 we can see what we obtained In fig. 3.2 we can see how it takes the agent more than 100000 episodes to start obtaining rewards higher than 400, and as the training goes on it progressively seems that gets some decays in the reward, only to achieve later on a higher one. About the duration of the episodes, it’s clear in fig. 3.3 how fast it is, which it also could be thanks to the simplicity of the action-state space in this case. Also both graphics are very similar, since the reward is the number of timesteps, so a higher rewards means that 21 CHAPTER 3. CARTPOLE ENVIRONMENT: AN INITIAL APPROACH Figure 3.2: Default CartPole Q-Learning: Average reward for every 2000 episodes. Figure 3.3: Default CartPole Q-Learning: Average duration for every 2000 episodes. Parameter Value Replay memory capacity 50000 Batch size 32 Update frequency 8 Number of timesteps before first update 0 Learning rate 0.001 Discount factor 0.99 Target network update weight 1 Target network sync frequency Every update Table 3.2: Default CartPole DQN: Parameters the episode went on for a longer time. 3.2.2 Default CartPole with DQN Now we will tackle the same problem but using a more complex algorithm, the DQN. This time, we will create our Tensorforce agent that will be trained by the application of the DQN algorithm. The parameters chosen for the algorithm are shown in table 3.2. We create a neural network consisting of two dense layers and a final linear layer as seen in (fig. 3.4), each of them with the parameters presented in table 3.3 and table 3.4. This time the agent was only trained for 10000 episodes, which took around 5.5 hours to Parameter Value Size 64 Trainable bias variable Yes Activation function Tanh Dropout 0 Initialization scale 1 Table 3.3: Default CartPole DQN: Dense layers parameters Parameter Value Size 2 Trainable bias variable Yes Initialization scale 1 Table 3.4: Default CartPole DQN: Linear layer parameters 22 CHAPTER 3. CARTPOLE ENVIRONMENT: AN INITIAL APPROACH Figure 3.4: Our neural network with two hidden dense layers of 64 neurons [29] Figure 3.5: Default CartPole DQN: Average reward for every 100 episodes. Figure 3.6: Default CartPole DQN: Average duration for every 100 episodes. complete, but as we show in fig. 3.5 and fig. 3.6, we got better results in fewer episodes compared to the Q-Learning training. This time we represented the average values for every 100 episodes since we only trained for 10000 episodes. But, in fig. 3.5, as soon as around 1100 episodes it starts getting a reward of 500, which is the maximum reward that the agent can get, and even though we get some down spikes in the average reward in some episodes, it also returns to achieving that maximum reward or at least a reward higher than 400 in the latter ones, concluding that the agent has perfected the technique of keeping the pole stabilized. Regarding the duration of the episodes, even though most of the episodes only take a little longer than 2 seconds, compared to the Q-Learning algorithm we can see how much more complex this algorithm is. But thanks to the simplicity of the CartPole problem, we get amazing results in much lesser episodes even though the training of each of them takes longer. Again, as it happened with the Q-Learning algorithm, it’s interesting how almost identical both graphics are, which makes sense since the reward is exactly the number of timesteps of the episode. 23 CHAPTER 3. CARTPOLE ENVIRONMENT: AN INITIAL APPROACH Figure 3.7: Example of extracted screen 3.3 CartPole with vision This approach differs mainly on the input that the agent receives, but the stopping conditions (excessive tilting of the pole or cart being far away from the center) and initial values of the environment are the same as the ones in Section 3.2. This time, instead of taking the numeric values that the environment provides, we will obtain the image of the environment and use it as input data for our agent. Thus, the environment needs to be rendered to get the pixel data. That way, we can extract the image in each state of the execution in order to train our agent. Note that there are some easily foreseeable problems when implementing this approach. The first one is the fact that many pixels do not actually change at all during the execution of an episode. An example of this are the white borders of the screen. There are also some pixels that may actually change at some point during the episode, but not in the near future, and thus are useless. An example of this is, if the cart is at the right side of the screen, the white pixels at the left of the image. Note that then we can actually eliminate pixels that never change without hurting the training of the agent. On the other hand, training solely on the pixels near to the cart is actually a trade-off, since the information about where on the screen is exactly the cart is lost, and only the nonpositional information about the cart is retained. However, it can diminish the memory and training time requirements. Another optimization can be done by realizing the fact that the agent may not learn well just by looking at still images of the cart, since many of the factors that could be essential to know are missing, such as the cart and pole speed. This can be partially fixed by taking into account the difference between a state and the one preceding it, instead of the image of the current state. This allows us to realize how much has the situation of the pole changed between an image and the next. Note once again how this does not allow us to know what the situation of the cart is in terms of speed or direction. Since we chose to center the picture around the cart to diminish the amount of input required, all images will find the cart in the same position, which means that it is unknown where it is going or how fast. Since Gym does not provide the RGB values of the CartPole graphic representation, we need to obtain them ourselves by rendering the environment and then using the torchvision [30] library, which allows us to get pixel data and perform all the posterior processing that has been stated earlier. This will allow us to transform the image into a 90x40x3 pixels 24 CHAPTER 3. CARTPOLE ENVIRONMENT: AN INITIAL APPROACH Parameter Value Replay memory capacity 10000 Batch size 32 Update frequency 8 Number of timesteps before first update 0 Learning rate 0.001 Discount factor 0.99 Target network update weight 1 Target network sync frequency Every update Exploration 0.05 Table 3.5: Vision CartPole DQN: Parameters Parameter Value Size 64 Trainable bias variable Yes Window size 3 Activation function ReLU Padding Same Stride 1 Dropout 0 Initialization scale 1 Table 3.6: Vision CartPole DQN: Convolutional layers parameters Parameter Value Pooling type Max Table 3.7: Vision CartPole DQN: Pooling layer parameters picture. Figure 3.7 exemplifies a CartPole screen generated after centering our image and removing far away pixels. The difference between two consecutive screens like this is then taken. Once we are able to do this, we need to create a custom Tensorforce Environment in which we will wrap the default Gym CartPole environment. While we will perform our actions in the internal environment, the state obtention will be overriden, and we will use differences of consecutive states images as the observations for our agent. 3.3.1 CartPole with vision applying DQN In this approach we resort to using a convolutional neural network, since we are dealing with the processing of images. First, the DQN algorithm parameters are shown in table table 3.5. The CNN consists in two 2-dimensional convolutional layers, followed by a pooling layer, and finally a linear layer, each of the layers with the parameters presented in table 3.6, table 3.7 and table 3.8. Compared to the previous two CartPole agents that we trained, this training was the more time-consuming to complete. The first 1000 episodes passed really fast since the agent would lose the episode almost instantly, but first due to the processing of each frame and 25 CHAPTER 3. CARTPOLE ENVIRONMENT: AN INITIAL APPROACH Parameter Value Size 2 Trainable bias variable Yes Initialization scale 1 Table 3.8: Vision CartPole DQN: Linear layer parameters Figure 3.8: Vision CartPole DQN: Average reward for every 100 episodes. Figure 3.9: Vision CartPole DQN: Average duration for every 100 episodes. then because of the agent keeping the pole from falling for longer periods of time as the training went on, training 1000 episodes would later take over 12 hours. In fig. 3.8 and fig. 3.9 we present the results obtained. Figure 3.8 shows that around 2500 episodes it starts achieving its best results, with rewards between 120 and 160, and the reward keeps going back and forth in that range for the following episodes. This means that the agent learns to keep the pole balanced for over 120 episodes, which doesn’t look too good compared with the results of the other two agents. Maybe the agent could achieve the perfect 500 timesteps after more episodes of training, but that would take days of keeping the agent training. The reason for this slower learning curve may be that, since we are only looking at the difference of the images, the agent can’t take into account factors like the cart velocity, the pole angular velocity and the position of the cart, so in this approach we might be losing 3 out of the 4 variables of the environment, and could also be the reason that a lot of the latter episodes would end because the cart would move too far from the starting point and not because of the pole falling. 3.4 Conclusions Now that we have taken three different approaches for dealing with the CartPole problem, we can comment on the difference of these three methods and the advantages and disadvantages of each of them. Starting with the default CartPole with Q-Learning approach, the first thing to note is how it is the one who needed the higher amount of episodes to achieve rewards higher than 400, which started happening at around 200000 episodes. But on the other hand, it worked really well with the simplicity of the problem, having only 4 variables to take into account, meaning that the training of each episode took less than 0.035 seconds, making 26 CHAPTER 3. CARTPOLE ENVIRONMENT: AN INITIAL APPROACH it the fastest of the three. Also, a different discretization of the states could have given us an even faster result. Using the DQN algorithm on the default CartPole proved to be a better approach episodewise. Since it’s a way more complex algorithm, the training took longer than the simpler Q-Learning algorithm. But on the other hand, in just less than 2000 episodes the agent learned how to almost perfectly keep the pole balanced. That is, because as it was briefly discussed in Section 2.2 the relationship between inputs and outputs that is learned by the neural network is able to infer the output on unseen inputs and therefore not all the state space is needed to be explored in order to reach a good outcome. Finally, the vision approach using DQN had a number of issues. The processing of each frame wasn’t very time-efficient, and taking the difference of two states, paired with removing unnecessary pixels to focus only on the cartpole, removed some of the information that we had about the cart itself in the environment, like its position and speed. Because of this the agent couldn’t take into account that moving too far from the starting point would make the episode end. All of these problems, and the slow training speed, forced us to stop the training at 5000 episodes, only achieving rewards around 140, which is a poor result compared to the two previous attempts using the values of the environment. 27 Chapter 4 Video game environments Once the CartPole environment has served its purpose as an introduction to the techniques and technologies used, we will tackle the main problem at hand, which is the training of agents that learn how to play video games. 4.1 Atari Environment The Atari 2600 console, released in 1977, achieved the first real success of a home video game console, selling over 30 million units, and as such was the first contact with video games for many, together with arcade machines. It has a good collection of some of the most classic and iconic video games, such as Pac-Man,Breakout,Space Invaders, or Frogger. Of course, Atari 2600 consoles incorporate hardware that nowadays we would consider strongly obsolete or insufficient, such as an 8 bit, 1.19 MHz MOS Technology 6507 processor, 128 bytes of RAM, and the ability to output at a 210x160 resolution. Games were played with a very basic joystick with four internal switches to encode directions, and an extra button for performing various actions in games. Despite its apparent simplicity, it is considered a challenging environment [31] for reinforcement learning. One could say that it has recently become less so with the creation of Deep-Q Networks [1], but the truth is that a lot of progress still needs to be made to fully consider Atari 2600 games as “solved problems”. Given their importance among the Artificial Intelligence community, many of the Atari 2600 games are conveniently wrapped as Gym environments. The Stella [32] emulator core used by Gym Retro actually allows wrapping of any Atari game as a Gym Retro environment, as long as an integration is already in the library, or is created and provided by the user. We will train a DQN agent that learns to play Space Invaders (see fig. 4.1) in its Atari 2600 version. We will do this in two fashions: first, by using RAM as a representation of our state, and then by using screen output. Note how, although the input values used to train the agents will be different, the output that they will generate is identical in shape, that is, both agents will choose an action out of the different button presses on a fictional Atari controller. Although many different button combinations are possible, for 28 CHAPTER 4. VIDEO GAME ENVIRONMENTS this environment Gym already restricts the agent to choosing only actions that actually do something in the game, and not strange ones such as pressing all buttons at the same time. Figure 4.1: Atari Space Invaders game The reward for an agent playing Space Invaders is immediately defined as the score obtained in the game. This makes a reasonable approach since the player is given points when defeating an enemy, which ultimately leads to the player completing screens and generating new ones in order to fight more enemies and obtain more points. Note that all the agents in the current chapter were trained in Google Colab Pro, since they required more RAM than the one installed in our machine. According to our tests, the agents were trained in a remote machine with 27.3 GB of RAM and an Intel(R) Xeon(R) CPU @ 2.20GHz. Now we will compare the similarities and differences of both approaches. 4.2 Atari with RAM values As said earlier, the Atari 2600 console comes with 128 bytes of RAM. This quantity that nowadays would seem ridiculously low has to contain values such as positions of enemies, number of lives left, positions of bullets, etc. This is one of the reasons why Atari 2600 games cannot have overly complex screens, since all the values that there would have to be kept would not fit in the RAM. The fact that the RAM has quite a small size compared with the screen rendering and contains a lot of relevant info about the game state makes it a potentially powerful input data to train an agent on. If the agent is able to grasp where the important values are, performance may be very positive, especially in comparison with the needed training time. However, there can be potential problems that interfere with this goal, such as the agent overfitting with values that are not actually as relevant as others. Given the positively low dimensionality of the states, no preprocessing is expected to be needed in order to train the DQN algorithm in reasonable times. There is also a theorical reason behind why performing preprocessing in RAM values is a dangerous task. While avoiding RAM values that we know are not relevant is possible, many of the techniques 29 CHAPTER 4. VIDEO GAME ENVIRONMENTS Figure 4.7: NES Space Invaders DQN with RAM: Average reward for every 20 episodes. Figure 4.8: NES Space Invaders DQN with RAM: Average duration for every 20 episodes. Figure 4.9: NES Space Invaders DQN with screen vision: Timesteps for every episode. Here are shown the average reward and episode duration every 20 episodes throughout the training process. The first big difference with the Atari version is shown on fig. 4.7. Here we see that the agent is stuck on more or less the same score interval throughout the whole training process, which may imply that the agent has not really learned anything very relevant yet and could improve with more episodes or with better parameter adjusting. By looking at fig. 4.8 we also find at a certain point the episode duration suddenly drops, perhaps because of a change in the cloud Colab environment. Then, the episode durations start sloping up progressively, which while one may think it is a result of the agent surviving longer each episode, it is not supported by an increase of timesteps according to fig. 4.9. The most reasonable explanation is once again an increase on the load of the Colab environment. By looking at the agent play, we intuitively perceive that the agent is having more trouble performing positive actions. It seems like it shoots more or less consistently, but that brings it into breaking the protections that defend the spaceship from shots. Sometimes, the best strategy it follows is sticking to a wall and shooting from there, which scores some points but also usually brings the agent to its death. It is obvious here that this is a step up in complexity from the Atari environment, but we 36 CHAPTER 4. VIDEO GAME ENVIRONMENTS Parameter Value Replay memory capacity 1000 Batch size 32 Update frequency 8 Number of timesteps before first update 0 Learning rate 0.001 Discount factor 0.99 Target network update weight 1 Target network sync frequency Every update Image preprocessing Image reduction + grayscaling State preprocessing Linear normalization Table 4.11: NES Space Invaders with vision: DQN Parameters will talk more about this in the conclusions. 4.6 NES with screen input The screen generated by the NES console is of 256x240 pixels, quite bigger than the one the Atari 2600 generates. This implies that probably many of the techniques that reduce the dimensionality of the states will probably be necessary again in order to achieve results on the task at hand. 4.6.1 NES vision with DQN Once again, all the previous work that applied to the vision Atari environment applies, since we needed to lower the dimension of the input in order to be able to achieve better times. Thus, screen size was cut in half, and color was turned into grayscale. Also, actions were reduced to moving left, moving right, and shooting, to favor the agent to perform useful actions. At table 4.11 the parameters for the DQN algorithm can be found, and at table 4.12, table 4.13 and table 4.14 the parameters of the layers of the network, that once again consists of two 2D convolutional layers followed by a pooling layer and the final action linear layer. We have included graphs that depict the training process of this agent, episode by episode up to 100, and for a total of almost 22 hours. In this experiment, despite seeing in fig. 4.10 that the agent also has some trouble learning a consistent technique to score points, we can make additional observations. Despite not being entirely similar, there is definitely a resemblance between fig. 4.10 and fig. 4.11, which implies that the agent is obtaining more points the longer it survives. This is further supported by fig. 4.12, which is almost identical to graph fig. 4.11. Observing the agent play, it is immediately clear that the agent still has a lot to learn. Many times it shoots its own protections. Sometimes it actually looks like it is able to avoid some bullets, but not always. It seems like this agent is able to avoid getting stuck in one of the two edges of the screen a bit more than the RAM agent. 37 CHAPTER 4. VIDEO GAME ENVIRONMENTS Parameter Value Size 64 Trainable bias variable Yes Window size 3 Activation function ReLU Padding Same Stride 1 Dropout 0 Initialization scale 1 Table 4.12: NES Space Invaders with vision: Convolutional layers parameters Parameter Value Pooling type Max Table 4.13: NES Space Invaders with vision: Pooling layer parameters Parameter Value Size 6 Trainable bias variable Yes Initialization scale 1 Table 4.14: NES Space Invaders with vision: Linear layer parameters We will proceed now to give some general conclusion of the chapter considering all of the previous results together. 4.7 Video game environments conclusion With all of this, we can finally compare all the agents and approaches and talk about their strengths and weaknesses. In general, it is pretty obvious that these were no toy problems and require lots of research, preparation, coding, and testing in order to get them working. Also, a powerful machine and a lot of time are needed to obtain meaningful results. We wonder if we could have obtained them with more training time, or if we had been able to use a powerful GPU Figure 4.10: NES Space Invaders DQN with screen vision: Reward for every episode. Figure 4.11: NES Space Invaders DQN with screen vision: Duration for every episode. 38 CHAPTER 4. VIDEO GAME ENVIRONMENTS Figure 4.12: NES Space Invaders DQN with screen vision: Timesteps for every episode. for the training. Of both approaches, the RAM versions of the environments are a clear improvement over vision versions in terms of training time needed, which means that it is easier to leave them training longer if necessary and will probably start obtaining results earlier. A correlation between input size and training time is found between the RAM Atari and NES versions, but is definitely not the only factor, considering that the second one is 16 times smaller than the first one but training time of each episode is only about 8 times bigger. About the vision versions, both of them increase incredibly the training time, with some episodes of the NES vision Space Invaders taking up to 1400 seconds, or 23 minutes, and this is after reducing state dimensionality. We can see that the rewards at this level are still not too far away from those of the RAM environments, but clearly further investigation is needed on this topic to decide which one can produce an agent that performs better, once again, with more training time and better resources. We would consider both problems to be still far from solved, but the fact that we were able to at least tackle them and obtain certain results is encouraging, and if resources and time are put into this field, this could certainly be a technique that can be used to solve problems of this kind of complexity in the mid term, and bigger ones in the long term. 39 Chapter 5 Explainable Deep Reinforcement Learning As previously discussed, one of the greatest disadvantages of using Deep Learning Methods it’s that we obtain a black-box model of which humans cannot obtain any explanations about its decisions. Advancements made in recent years in the field of Deep Reinforcement Learning are promising but its results can not be put in a real world scenario, since its implementation on physical systems can be dangerous for humans without adequate policing and supervision by a knowledgeable expert. 5.1 Saliency maps Explainable Artificial Intelligence (XAI) and Interpretable Machine Learning are the two main areas that focus on this challenge. On this work we shall focus on examining an approach to explain the behaviour of the models which utilize visualization methods. For this kind of problem, the most common interpretation model are saliency maps [33]. The main idea behind saliency maps is to highlight which pixels from the input image are the most relevant for a given decision. As a result of this process, a heat map can be generated on top of the input image so that anyone with the proper context can get an intuition behind how the agent is making its decisions. There are several ways of generating saliency maps, but they can be grouped into three main categories: •Gradient-based: These methods use the gradient of the network with respect to each of its inputs to quantify how much small changes in them impact the decision made. •Propagation-based: These methods use modified propagation rules to get how much did each neuron amount to the final decision, considering intermediate results of the prediction. •Perturbation-based: These make changes to areas of the input image and measure how much they impact the output. All of them have been applied to Deep Reinforcement Learning, nevertheless, consider40 CHAPTER 5. EXPLAINABLE DEEP REINFORCEMENT LEARNING Figure 5.1: Overview of the RISE explanation process [34] ing the trend in recent years is to use Perturbation-based saliency maps, we will implement this kind in our work. One major advantage to support this decision is that these approaches are model-agnostic and therefore seamlessly implemented without any adjustment regardless the agent it is used on. 5.2 RISE We have decided to apply the RISE (Randomized Input Sampling for Explanation of Black-box Models) [34] method to our agents, in hopes of getting a deeper understanding of what it is taking into account to make its decisions. The main reason to support this choice is that it takes a general approach to model explanation, that is, it can generate saliency maps regardless of the network architecture and with no need to access its internals, parameters or gradients therefore completely decoupling the training and explaining processes that entail this project. The RISE method was initially developed for an image classification model (ResNet50) but promising results for Atari games have also been obtained in [33]. In order to discuss our adaptation of the method to be used on our agents we shall first discuss the basics behind its original implementation. The key idea of this method is to probe the model by repeatedly querying it with modified versions of the input image via a masking process; once the results of this queries are collected, the importance of each part of the image to the output of the model can be calculated (fig. 5.1). Formally, the black box model can be expressed as a function f:I → Rnthat for each input I∈ I produces a scalar confidence score for each of the npossible classes it classifies. Where I={I|I:G→R3}is the space of color images, being Ia function that maps the coordinates G={1, . . . , H}×{1, . . . , W}of each pixel to its RGB value. Once the model has been properly defined, we shall overview the detailed theory behind the method. First, the generation of random masks: One initial, na¨ıve way, could be to set each individual pixel of the input-sized mask either to 1 or 0 with probabilities pand (1 −p) respectively. However, this manner may present several disadvantages: the mask space (of all possibly-generated masks) has size 2H×W, which means it needs a bigger sample 41 CHAPTER 5. EXPLAINABLE DEEP REINFORCEMENT LEARNING set to reach a good estimation; and a small change in pixel values may cause a significant shift in the model’s output. Therefore, to avoid this issues bilinear upsampling is used generating non-binary masks in [0,1] by performing the following procedure: 1. Nbinary masks of size h×w, (h < H, w < W ) are generated by setting each element independently to 1 or 0 with probability pand (1 −p) respectively. In the implementation code, this is done by the declaration of an additional variable s, which is used to calculate hand was g(H) and g(W) where g(x) = ⌈x s⌉. 2. All masks from the previous are upsampled to size (h+ 1)CH×(w+ 1)CW, where CH×CW=⌊H h⌋×⌊W w⌋, using bilinear interpolation. 3. Masks are shifted using uniformly random indents from (0,0) up to (CH, CW) Now, we shall describe how the importance of each pixel is obtained: Let Midenote the i-th mask generated using the previous procedure, and let Mi(λ) be the value of Mifor the pixel λ∈G. The importance of the pixel λ, on the input image Iand the black-box model fis: SI,f (λ) = 1 p·N N X i=1 f(I◦Mi)·Mi(λ) (5.1) Where ”◦” is the Hadamard product, (A◦B)ij =Aij ·Bij (for a full explanation of eq. (5.1) see [34]). 5.3 RISE for Deep Q-Learning Concerning the use of the previous technique in our work, the principal challenge to address is the difference between the output of an image classifier and a DQL agent. Whereas image classification models give a confidence score (probability) for each of the classes in the model and takes the highest one as its prediction, DQN networks determine certain Q-values for each possible action being the output and the action taken by the agent, the one with the highest value. To overcome this problem we intend to normalize the Q-values of the output vector of our model so that they can be treated as a probability distribution. For that purpose, the softmax (σ) [35] function is used. This function, takes a vector z= (z1, . . . , zK) of real numbers as input, and normalizes it into a probablity distribution of Kvalues proportional to the elements of z, that is, σ:RK→(0,1)K,K > 1, where: σ(z)i=ezi PK j=1 ezj for j= 1, . . . , K (5.2) Once this issue has been addressed, the revised version of eq. (5.1) can be written including eq. (5.2) as follows: SI,f (λ) = 1 p·N N X i=1 σ[f(I◦Mi)] ·Mi(λ) (5.3) 42 CHAPTER 5. EXPLAINABLE DEEP REINFORCEMENT LEARNING 5.3.1 Explaining CartPole with vision As a proof of concept, the RISE explanation schema described by eq. (5.3) is applied to the agent for Cartpole with vision trained using DQN in Chapter 3. For that purpose and to facilitate future implementations, a notebook (.ipynb) is created with the full implementation of all the methods needed to create, run and generate the explanations for any tensorforce agent. Once the experiment has been run, some conclusions can be drawn from the saliency maps about the agent’s behaviour: Figure 5.2: CartPole: examples of saliency maps where the agent’s focus is on key parts of the image Figure 5.2 shows that the agent focus on the variation of the position of either the car or the pole to make the decision of what move to make next. Being a rule of thumb that when the pole is leaning left it chooses the ”LEFT” action, even though sometimes it chooses to move to the right, perhaps because the position of the cart is too far to the left. This kind of high-level explanation can be easily understood by a human participant with sufficient context. In contrast (fig. 5.3), other generated graphics show that for certain state, the agent does not have sufficient training and fails to identify the “relevant information”, or confuses it with other parts of the image: Figure 5.3: CartPole: examples of saliency maps where the agent fails to identify relevant information 43 CHAPTER 5. EXPLAINABLE DEEP REINFORCEMENT LEARNING 5.3.2 Explaining video game environents Once the method has been tested against the toy example, it is imperative to know how it works when presented with the agents trained in Chapter 4. For each agent, the same process as in section 5.3.1 is implemented and the results presented in the same, orderly manner: Atari with screen input Figure 5.4: Atari: examples of saliency maps where the agent’s focus is on key parts of the image Figure 5.5: Atari: examples of saliency maps where the agent fails to identify relevant information Figure 5.4 shows examples of input screens where the agent focused on a region where the enemy was present just above the players position. In this case, we can hypothesize that in these situations the agent chooses to ”FIRE” at the enemy at that location. Though, most of the results obtained were closer to those of Figure 5.5 where no clear conclusion can be drawn. 44 CHAPTER 5. EXPLAINABLE DEEP REINFORCEMENT LEARNING NES with screen input Figure 5.6: NES: examples of saliency maps where the agent’s focus is on key parts of the image Figure 5.7: NES: examples of saliency maps where the agent fails to identify relevant information While we are still able to obtain images where the agent is clearly looking at the right part of the picture (see fig. 5.6), the number of saliency maps where this is not obvious actually grows more and more as we increase the complexity of the environment (see fig. 5.7). And a similar analysis as in the Atari environment can be made. This is probably because the agents still need to undergo more learning to get better at these more complex tasks. 5.3.3 Conclusions As seen on this chapter, this technique allows us generate visual explanations on the behaviour of agents using Deep Neural Networks by observing their behaviour given different inputs. While some results look very promising, others were far from satisfactory, specially for the video game environments. One could argue that it is because of the method not being suitable enough for the problem at hand, but looking at results obtained in [33] it seems that it is not the full explanation. If we were to compare the agent’s performance on the last two problems to the performance of the CartPole agent, an alternative explanation can be drawn: since they are not as good as the latter at solving the problem (playing the game), the knowledge they have about the environment is less accurate and therefore the explanations are not as clean and rather fuzzy. So, to sum up, this kind of explanation not only lets us know what the most important part of the image is for well-trained agents, but it may let us discover lacking agents too. 45 APPENDIX A. PERSONAL CONTRIBUTIONS TO THE PROJECT A.2 Manuel Llorca Ron At the beginning of the project, I did a general research on the topic of reinforcement learning, deep learning, neural networks... as well as the current state of the art. This allowed me to both refresh my knowledge of the subject and to understand which were the areas in which we should focus when preparing our following work. All this theorical pre-work allowed me to write many of the general ideas of the introduction of Chapter 1, as well as the posterior objectives and the workplan. We then needed to decide some of the tools and libraries with which we would tackle the problem. We divided the work and investigated about different Python reinforcement learning libraries each. I learned about Keras and Tensorforce, and then discussed together with my colleagues the advantages and disadvantages of each one before choosing Tensorforce. As for Chapter 2, we also divided the concepts that each would write about. I focused more on the part of the technologies, writing Section 2.5 about Gym, Section 2.6 about GymRetro, Section 2.7 about Tensorforce, and Section 2.8 about Colab, but also helped writing certain parts of other sections, such as the introductions of Section 2.1,Section 2.2, and Section 2.3. To be able to actually start with the practical part of the project, I started toying with various small reinforcement learning and deep reinforcement learning examples, which helped me familiarize myself with the syntax of the libraries and tools, as well as understanding how to put the theory of the algorithms we had learnt into practice. Then I studied in detail how the CartPole environment works in Gym, which allowed me to write about it (Chapter 3, especially the theory at the beggining of the chapter and of Section 3.2 and Section 3.3). I then also prepared the code for training a Tensorforce DQN agent in the default version of CartPole, as well as adapting the environment to work with the generated images as states for the vision version, after some trial and error. Once we had the CartPole example working and considered that we had solved that problem, we focused on the posterior environments. I performed some testing with GymRetro until I was able to successfully try out and control various video games. This also allowed me to compare the differences and similarities with a standard Gym environment, and understand the code that we would need to implement. In collaboration with Manuel Ortega, we prepared the code to train DQN agents on all the environments, and we agreed that he would train the Atari RAM agent, since that could be done in a normal Colab environment, and that I would train the rest of the agents in a High RAM Colab environment, as well as trying to enable GPU usage. We also explored some fields such as the GymRetro integration tool, which helps redefining values such as the reward given or the done condition of the video game, but ultimately decided to stick with the default integration for Space Invaders, since it was provided in a way that made sense for the training. All of this was without any doubt one of the most tedious processes of the whole work. Since training took a very long time, every time we misconfigured something, or an error occurred, we needed to repeat a lot of previous work, which resulted on long debugging sessions. This also happened when trying to use a GPU on Google Colab, since we needed to constantly try different approaches to match the needed versions, with none of them 52 APPENDIX A. PERSONAL CONTRIBUTIONS TO THE PROJECT ultimately working, which also made us lose some precious time. Finally, we managed to strike a balance between performance and training time, and decided to train those agents for as long as we could to extract conclusions from the process. That allowed me to write the theory in the environments of Chapter 4, and also the process and results of training the agents, such as the steps taken in order to reduce dimensonality in vision environments, or the discretization of actions in the NES environment to simplify the output layer. After this, I wrote the conclusion of that chapter comparing all the agents and finding the similarities and the differences. As for the explainability part of the video game agents, I helped Mar´ıa with the Atari and NES environments, executing the code and obtaining the pictures finally uploaded. Finally I helped creating and preparing our final repository with clean versions of the code and agents and adding it to this memory. I wrote some of the conclusions in Chapter 6 and this appendix to wrap up my work. 53 APPENDIX A. PERSONAL CONTRIBUTIONS TO THE PROJECT A.3 Manuel Ortega Salvador The first steps were researching the main elements of the project, like reinforcement learning, deep learning and neural networks, as well as some of the algorithms related to these topics, in order to get a better understanding on the current state of these techniques and to help us organize our work, knowing which parts were easier to tackle at first and which ones would need more time and work to complete. Another of the first things I did was install GymRetro on my computer, and explore the options that it offered, as well as investigate about the integration of games and how the tool had access to important variables located in the memory of each game, just in case that was something that would be needed to change or customize later on when we would be training agents in one of those games. This also made be understand better the concept of policies, since the platform had some deafult ones that you could apply to an agent and watch it play, so that resulted to be very convenient and was a very productive experience. Then we needed to find Python libraries that would help us in the tasks of reinforcement learning, so we divided the work on finding one that would allow us to do everything we needed, and also one that was easy to work with and understand. I was tasked with looking into the PyTorch library, and even though we ended up not using it in our work, I was able to find a paper which included an open source solution to training an agent in the CartPole environment, taking as input the whole screen instead of the internal values of the environment. We were able to adapt the part of the code were it retrieves an image of the screen of the environment and applies some modifications to make it easier to process it during the training, which make everything easier since at the time we didn’t know a way to achieve this, and was a key part in that problem since Gym didn’t offer a way to do it without doing it manually yourself. Regarding Chapter 1, I wrote the introduction regarding XAI, as well as the state of the art, even though all of that was later explained further by Mar´ıa in Chapter 5. Then in Chapter 2 I took care continuing in Section 2.1 after the introduction written by Manuel Llorca, completing the section explaining the concept of MDP and its elements, as well as presenting what the general objective of the agent is and ways to achieve that objective via a policy or a value function. Then I continued the section explaining the Q-Learning algorithm, how it works and its different parameters, as well as adding to the explanation with an application of the algorithm in the simple environment Frozen Lake, trying to show with this simple example how the values of the Q-table are updated through the training, and showing the importance in this type of problems of allowing the agent to explore the environment at first and later on prioritizing exploitation of the actions deemed to be the best at that point. After that I continued with Section 2.3, which later was revised and completed by Manuel Llorca, and finally I offered an explanation of the DQN algorithm in the same fashion as with the Q-Learning. Getting into the more practical part of the project, first I explored the CartPole environment to try to familiarize myself with the algorithms and how the agent learns in a not so complex environment. Then I took the code of the CartPole with Q-Learning prepared by Mar´ıa, and the DQN code for the default CartPole and the vision approach adapted by Manuel Llorca, and trained agents for those three versions, as well as gathering data of the training which was later presented and written by me in Section 3.2.1,Section 3.3.1. 54 APPENDIX A. PERSONAL CONTRIBUTIONS TO THE PROJECT After that we moved onto a more complex problem: training an agent for both the Atari and the NES versions of Space Invaders, taking the two approaches of using the values of the RAM as the information for the training, or the vision approach using directly the image of the game. Since the Atari RAM agent was the only one that I was able to train in a standard Colab environment, I did the training and the consequent recovery of data of the agent, while Manuel Llorca trained the rest of the agents. As I did with the CartPole agents that I trained, I presented and reviewed the results obtained by this agent in Section 4.2. 55 Bibliography [1] V. Mnih, K. Kavukcuoglu, D. Silver, et al. “Human-level control through deep reinforcement learning”. In: Nature 518 (2015), pp. 529–533. [2] IBM Cloud Education. History of artificial intelligence: Key dates and names. Accessed on 03/02/2022. 2020. url:https://www.ibm.com/cloud/learn/what-isartificial-intelligence#toc-history-of--2jPgsXm. [3] J. Liebowitz. The Handbook of Applied Expert Systems. CRC Press, 2019. isbn: 9780429612497. url:https://books.google.es/books?id=WzX3DwAAQBAJ. [4] Y. Li. Deep Reinforcement Learning: An Overview. 2017. doi:10.48550/ARXIV. 1701.07274.url:https://arxiv.org/abs/1701.07274. [5] A. Nichol, V. Pfau, C. Hesse, et al. “Gotta Learn Fast: A New Benchmark for Generalization in RL”. In: arXiv preprint arXiv:1804.03720 (2018). [6] L. Wells and T. Bednarz. “Explainable AI and Reinforcement Learning—A Systematic Review of Current Approaches and Trends”. In: Frontiers in Artificial Intelligence 4 (2021). issn: 2624-8212. doi:10.3389/frai.2021.550030.url:https: //www.frontiersin.org/article/10.3389/frai.2021.550030. [7] F. Schwendicke, W. Samek, and J. Krois. “Artificial Intelligence in Dentistry: Chances and Challenges”. In: Journal of Dental Research 99 (Apr. 2020), p. 002203452091571. doi:10.1177/0022034520915714. [8] J. Fan, Z. Wang, Y. Xie, et al. A Theoretical Analysis of Deep Q-Learning. 2019. doi:10.48550/ARXIV.1901.00137.url:https://arxiv.org/abs/1901.00137. [9] G. Brockman, V. Cheung, L. Pettersson, et al. OpenAI Gym. 2016. eprint: arXiv: 1606.01540. [10] A. Kuhnle, M. Schaarschmidt, and K. Fricke. Tensorforce: a TensorFlow library for applied reinforcement learning. Web page. Accessed on 16/02/2022. 2017. url: https://github.com/tensorforce/tensorforce. [11] R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. Second. The MIT Press, 2018. url:http://incompleteideas.net/book/thebook2nd.html. [12] C. Watkins and P. Dayan. “Technical Note: Q-Learning”. In: Machine Learning 8 (May 1992), pp. 279–292. doi:10.1007/BF00992698. [13] M. Labonne. Q-learning for beginners. Accessed on 13/04/2022. Mar. 2022. url: https://towardsdatascience.com/q-learning-for-beginners-2837b777741. [14] Y. LeCun, Y. Bengio, and G. Hinton. “Deep learning”. In: nature 521.7553 (2015), pp. 436–444. [15] Himanish Shekhar Das and Pinki Roy. Deep Neural Network. Accessed on 17/03/2022. 2020. url:https://www.sciencedirect.com/topics/computer-science/deepneural-network. 56 BIBLIOGRAPHY [16] S. Verma. Understanding different loss functions for neural networks. Accessed on 15/05/2022. Oct. 2021. url:https://shiva-verma.medium.com/understandingdifferent-loss-functions-for-neural-networks-dd1ed0274718. [17] A. Kathuria. Intro to optimization in Deep learning: Gradient descent. Accessed on 15/05/2022. Dec. 2020. url:https://blog.paperspace . com / intro - to - optimization-in-deep-learning-gradient-descent/. [18] V. Bushaev. Adam-latest trends in deep learning optimization. Accessed on 15/05/2022. Oct. 2018. url:https://towardsdatascience.com/adam-latest-trends-indeep-learning-optimization-6be9a291375c. [19] Amber. Zero to one: (DEEP) Q-learning, PART1, basic introduction and implementation. Accessed on 14/04/2022. Apr. 2019. url:https : / / medium . com / @qempsil0914/zero-to-one-deep-q-learning-part1-basic-introductionand-implementation-bb7602b55a2c. [20] O.-M. Camburu. “Explaining Deep Neural Networks”. In: (2020). doi:10.48550/ ARXIV.2010.01496.url:https://arxiv.org/abs/2010.01496. [21] S. Lundberg and S.-I. Lee. A Unified Approach to Interpreting Model Predictions. 2017. doi:10.48550/ARXIV.1705.07874.url:https://arxiv.org/abs/1705. 07874. [22] S. Greydanus, A. Koul, J. Dodge, et al. Visualizing and Understanding Atari Agents. 2017. doi:10.48550/ARXIV.1711.00138.url:https://arxiv.org/abs/1711. 00138. [23] Libretro API. Accessed on 15/02/2022. url:https://www.libretro.com/index. php/api/. [24] Mart´ın Abadi, Ashish Agarwal, Paul Barham, et al. TensorFlow: Large-Scale Machine Learning on Heterogeneous Systems. Accessed on 16/02/2022. 2015. url: https://www.tensorflow.org/. [25] F. Chollet et al. Keras.https://keras.io. Accessed on 16/02/2022. 2015. [26] A. Paszke, S. Gross, F. Massa, et al. “PyTorch: An Imperative Style, High-Performance Deep Learning Library”. In: Advances in Neural Information Processing Systems 32. Ed. by H. Wallach, H. Larochelle, A. Beygelzimer, et al. Curran Associates, Inc., 2019, pp. 8024–8035. url:http://papers.neurips.cc/paper/9015-pytorchan-imperative-style-high-performance-deep-learning-library.pdf. [27] N. Tasfi. PyGame Learning Environment.https://github.com/ntasfi/PyGameLearning-Environment. Accessed on 12/02/2022. 2016. [28] E. Bisong. “Google Colaboratory”. In: Building Machine Learning and Deep Learning Models on Google Cloud Platform: A Comprehensive Guide for Beginners. Berkeley, CA: Apress, 2019, pp. 59–64. isbn: 978-1-4842-4470-8. doi:10.1007/978-14842-4470-8_7.url:https://doi.org/10.1007/978-1-4842-4470-8_7. [29] NN-svg. Accessed on 12/05/2022. url:http://alexlenail.me/NN-SVG/index. html. [30] S. Marcel and Y. Rodriguez. “Torchvision the Machine-Vision Package of Torch”. In: Proceedings of the 18th ACM International Conference on Multimedia. MM ’10. Firenze, Italy: Association for Computing Machinery, 2010, pp. 1485–1488. isbn: 9781605589336. doi:10.1145/1873951.1874254.url:https://doi.org/10. 1145/1873951.1874254. [31] M. G. Bellemare, Y. Naddaf, J. Veness, et al. “The Arcade Learning Environment: An Evaluation Platform for General Agents”. In: CoRR abs/1207.4708 (2012). arXiv: 1207.4708.url:http://arxiv.org/abs/1207.4708. 57 BIBLIOGRAPHY [32] ”A multi-platform Atari 2600 VCS emulator”. Accessed on 03/02/2022. url:https: //stella-emu.github.io/. [33] T. Huber, B. Limmer, and E. Andr´e. “Benchmarking Perturbation-based Saliency Maps for Explaining Atari Agents”. In: (2021). doi:10.48550/ARXIV.2101.07312. url:https://arxiv.org/abs/2101.07312. [34] V. Petsiuk, A. Das, and K. Saenko. “RISE: Randomized Input Sampling for Explanation of Black-box Models”. In: CoRR abs/1806.07421 (2018). arXiv: 1806.07421. url:http://arxiv.org/abs/1806.07421. [35] Wikipedia contributors. Softmax function — Wikipedia, The Free Encyclopedia. Accessed on 13/02/2022. 2022. url:https://en.wikipedia.org/w/index.php? title=Softmax_function&oldid=1079739974. 58