Deep_Reinforcement_Learning_Part_5_.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Deep Reinforcement Learning- Part-5 .ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ZEWIeEYp25q2",
        "colab_type": "text"
      },
      "source": [
        "This is the Part-4 of Deep Reinforcement Learning Notebook series.***In this Notebook I have talked about some problems we have while using the Deep Q-Networks algorithm (DQN) and how we can improve DQN***.\n",
        "\n",
        "\n",
        "The Notebook series is about Deep RL algorithms so it excludes all other techniques that can be used to learn functions in reinforcement learning and also the Notebook Series is not exhaustive i.e. it contains the most widely used Deep RL algorithms only.\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GKqblIxB3CfE",
        "colab_type": "text"
      },
      "source": [
        "# Target Networks\n",
        "We saw in the last notebook that we calculate target q-values by the reward of taking that action at that state plus the discounted highest Q value for the next state. We know that during training the Q-network\n",
        "parameters θ are adjusted to minimize the difference between predicted and target q-values but this is difficult when target q-values changes each training step. So, we’re getting closer to our target but the target is also moving. It’s like chasing a moving target! This lead to a big oscillation in training. It’s like if you were a cowboy (the Q estimation) and you want to catch the cow (the Q-target) you must get closer (reduce the error). At each time step, you’re trying to approach the cow, which also moves at each time step (because you use the same parameters). This leads to a very strange path of chasing (a big oscillation in training) and hence results in unstable training.\n",
        "\n",
        "![alt text](https://github.com/Machine-Learning-rc/Unimportant/blob/master/Screenshot%202020-07-19%20at%2012.11.42%20PM.png?raw=true)\n",
        "\n",
        "Now here we see our first improvement technique for DQN i.e. target Networks. It was introduced by Mnih et. al. in Human-level Control through Deep Reinforcement Learning. To reduce the changes target Q-values in between training steps we use a target network. A target network is a second network with parameters φ and is a lagged copy of the Q-network(this is the network we are training and using for predicted q-values). The target network $Q^{π_φ}(s, a)$ is used to calculate target q-values instead of the Q-network which is continuously changing. Periodically φ is updated to the current values for θ. This is known as a replacement update. The update frequency for φ is problem-dependent.For example, in the Atari games, it is common to update φ every 1, 000 – 10, 000 environment steps. For simpler problems, it is not necessary to wait as long. Updating φ every 100 – 1, 000 will be sufficient.\n",
        " "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ViT2tka47okE",
        "colab_type": "text"
      },
      "source": [
        "# Why Target Networks help to stabilize training?\n",
        "Every time $Q_{tar}^{π_θ}(s, a)$ is calculated, the Q-function represented by the parameters θ will be slightly different, and so $Q_{tar}^{π_θ}(s, a)$ may be different for the same (s, a). It is possible that between one training step and the next, $Q_{tar}^{π_θ}(s, a)$ differs significantly from the previous estimate. This “moving target” can de-stabilize training because it makes it much less clear what values a network should be trying to approach. Introducing a target network stops the target from moving. In between updating φ to θ, φ is fixed and so the Q-function represented by φ doesn’t change. This transforms the problem into a standard supervised regression in between the updates to φ. Whilst this does not fundamentally change the underlying optimization problem, a target network helps to stabilize training, and make divergence or oscillation of the policy less likely. Periodically replacing the target network parameters φ with a copy of the network parameters θ is a common way to perform the update. Alternatively each time step, φ can be set to a\n",
        "weighted average of φ and θ. This is known as a Polyak update and can be thought of as a “soft update”.The main advantage of a replacement update is that φ is fixed for several steps which temporarily eliminates the “moving target”. In contrast, when using a Polyak update, φ changes each training iteration but more gradually than θ. However, a replacement update has the quirk of introducing a dynamic lag between φ and θ which depends on the number of time steps since the last update of φ. A Polyak update doesn’t have this feature. The mix between φ and θ is constant. One disadvantage of target networks is that they can slow down training since $Q_{tar}^{π_θ}(s, a)$ is generated from the older target network. If φ and θ are too close, then training may be unstable. However if φ changes too slowly then training may be unnecessarily slow. The hyper-parameter which controls how fast φ changes needs to be tuned to find a good balance between stability and training speed.\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "2mBUiLt980z5",
        "colab_type": "text"
      },
      "source": [
        "# DQN with target Networks\n",
        "![alt text](https://github.com/Machine-Learning-rc/Unimportant/blob/master/Screenshot%202020-07-17%20at%207.08.06%20PM.png?raw=true)\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "YBHjS4vU95mB",
        "colab_type": "text"
      },
      "source": [
        "# DOUBLE DQN\n",
        "Double DQNs, or double Learning, was introduced by Hado van Hasselt in the paper Deep Reinforcement Learning with Double Q- learning. This method handles the problem of the overestimation of Q-values. So let us first understand what is this problem?\n",
        "\n",
        "In DQN, we construct $Q_{tar}(s,a)$ by selecting the maximum Q- value estimate in next-state.Now we face a simple problem: how are we sure that the best action for the next state is the action with the highest Q-value?\n",
        "We know that the accuracy of q values depends on what action we tried and what neighboring states we explored. As a consequence, at the beginning of the training, we don’t have enough information about the best action to take. Therefore, taking the maximum q value (which is noisy) as the best action to take can lead to false positives. If non-optimal actions are regularly given a higher Q value than the optimal best action, the learning will be complicated.\n",
        "\n",
        "In the paper Deep Reinforcement Learning with Double Q- learning van Hasselt et. al. showed that if $Q^{π_θ}(s′, a′)$ contain any errors, then max $Q^{π_θ}(s′, a′)$ will be positively biased and the resulting Q-values will be overestimated. Unfortunately, there are many reasons why $Q^{π_θ}(s′, a′)$ will not be exactly correct. Function approximation using a neural network is not perfect, an agent may not fully explore the environment, and the environment itself may be noisy. We should, therefore, expect $Q^{π_θ}(s′, a′)$ to contain some error and so the Q-values will be overestimated. Furthermore, the more actions there are to choose from in-state s′, the greater the overestimation is likely to be. \n",
        "\n",
        "The solution is: when we compute the Q target, we use two networks to decouple the action selected from the target Q value generation. We:\n",
        "\n",
        "\n",
        "*  use our DQN network to select what is the best action to take for the next state (the action with the highest Q value).\n",
        "*  use our target network to calculate the target Q value of taking that action at the next state.\n",
        "\n",
        "![alt text](https://github.com/Machine-Learning-rc/Unimportant/blob/master/Screenshot%202020-07-17%20at%207.20.34%20PM.png?raw=true)\n",
        "\n",
        "The DQN algorithm uses the same network θ to select action a′ and to evaluate the Q-function for that action. Double DQN uses two different networks, θ, and φ. θ is used to select a′, and φ is used to calculate the Q-value for (s′, a′)\n",
        "\n",
        "In the last section, we saw target networks so we already have two networks; the training network θ and the target network φ.θ and φ have been trained with overlapping experiences, but if the number of time steps between setting φ = θ is large enough, then in practice they are sufficiently different to function as the two different networks for Double DQN. The training network θ is used to select the action. This is important to ensure that we are still learning the optimal policy after introducing the Double DQN modification. The target network φ is used to evaluate that action. This is how we can combine Double DQN with target networks"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "NRDJNnUcD-fv",
        "colab_type": "text"
      },
      "source": [
        "# Double DQN combined with target network\n",
        "![alt text](https://github.com/Machine-Learning-rc/Unimportant/blob/master/Screenshot%202020-07-17%20at%207.31.26%20PM.png?raw=true)\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8uazP1yCFWkn",
        "colab_type": "text"
      },
      "source": [
        "#Prioritized Experience Replay\n",
        "Prioritized Experience Replay (PER) was introduced in 2015 by Tom Schaul. The idea is that some experiences may be more important than others for our training, but might occur less frequently.\n",
        "If we can train an agent by sampling informative experiences more frequently than uninformative ones, the agent may learn faster. Because we sample the batch uniformly (selecting the experiences randomly) these rich experiences that occur rarely have practically no chance to be selected. That’s why, with PER, we try to change the sampling distribution by using a criterion to define the priority of each tuple of experience. Consider the following example. A humanoid agent is trying to learn how to stand. At the beginning of each episode, the agent is always initialized sitting on the floor. Initially, most actions will result in the agent flailing around on the ground, and only a few experiences will convey meaningful information about how to combine joint movements so as to balance and stand up. These experiences are more important for learning how to stand than those in which the agent is stuck on the ground. They help the agent learn what to do instead of the many ways it can do the wrong thing.\n",
        "\n",
        "\n",
        "Prioritized Experience Replay is based on this simple and intuitive idea, but presents two implementation challenges. First, how to automatically assign each experience a priority. Second, how to sample efficiently from the replay memory using their priorities.\n",
        "\n",
        "A natural solution to the first problem is for the priority to be derived from the absolute difference between $Q^{π_θ}(s, a)$ and $Q^π_{tar}(s, a)$\n",
        ", known as the TD error. The larger the difference between these two values, the larger the mismatch between an agent’s expectations and what happened in the next step, and the more an agent should correct $Q^{π_θ}$(s, a). The only remaining issue is what priority to assign to experiences initially since there is no TD error available. Typically this is solved by setting the score to a large constant value to encourage each experience to be sampled at least once.\n",
        "\n",
        "Schaul et al. propose two different options for sampling using the scores; rank-based, and proportional prioritization. Both approaches are based on an interpolation between greedy prioritization (always picking the experiences with the top n scores) and uniform random sampling. This ensures that experiences with higher scores are sampled more often whilst ensuring that each experience has a non zero probability of being sampled.\n",
        "\n",
        "We define the probability of sampling transition i as\n",
        "\n",
        "![alt text](https://github.com/Machine-Learning-rc/Unimportant/blob/master/Screenshot%202020-07-19%20at%201.07.28%20PM.png?raw=true)\n",
        "\n",
        "Equation 5.1\n",
        "\n",
        "The first variant we consider is the direct, **proportional prioritization** where $p_i$ = |$δ_i$| + ε, where ε\n",
        "is a small positive constant that prevents the edge-case of transitions not being revisited once their\n",
        "error is zero. The second variant is an indirect, **rank-based prioritization** where $p_i$ = 1/rank(i) , where \n",
        "rank(i) is the rank of transition i when the replay memory is sorted according to $|δ_i|$. In this case, P becomes a power-law distribution with exponent α. Both distributions are monotonic in |δ|, but the latter is likely to be more robust, as it is insensitive to outliers.\n",
        "\n",
        "# Importance Sampling\n",
        "Prioritizing certain examples changes the expectation of the entire data distribution, which introduces bias into the training process. This can be corrected by multiplying the TD error for each example by a set of weights, known as importance sampling. If the bias is small then it is unclear how effective importance sampling is because there are other factors such as the action noise and a highly non-stationary data distribution, that may dominate the effect of a small bias especially in the early stages of learning. Schaul et. al. hypothesize that correcting for the bias is only likely to matter towards the end of the training, and show that the effect of making the correction is mixed. In some cases adding importance sampling led to improved performance, in others, it made little difference or caused performance to deteriorate.\n",
        "\n",
        "\n",
        "Importance sampling has another benefit when combined with prioritized replay in the context of non-linear function approximation (e.g. deep neural networks): here large steps can be very disruptive, because the first-order approximation of the gradient is only reliable locally, and have to be prevented with a smaller global step-size. In our approach instead, prioritization makes sure high-error transitions are seen many times, while the IS correction reduces the gradient magnitudes (and thus the effective step size in parameter space), and allowing the algorithm to follow the curvature of highly non-linear optimization landscapes because the Taylor expansion is constantly re-approximated.\n",
        "\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "l9I9A6hgMXOo",
        "colab_type": "text"
      },
      "source": [
        "# Implementation of PER\n",
        "First of all, we can’t just implement PER by sorting all the Experience Replay Buffers according to their priorities. This will not be efficient at all due to O(nlogn) for insertion and O(n) for sampling. We need to use another data structure instead of sorting an array — an unsorted sumtree. A sumtree is a Binary Tree, which is a tree with only a maximum of two children for each node. The leaves (deepest nodes) contain the priority values, and a data array that points to leaves contains the experiences.\n",
        "\n",
        "Updating the tree and sampling will be really efficient (O(log n)).\n",
        "\n",
        "If you don't have knowledge about tress then check out this video: https://youtu.be/oSWTXtMglKE\n",
        "\n",
        "Look at this https://jaromiru.com/2016/11/07/lets-make-a-dqn-double-learning-and-prioritized-experience-replay/ article for more clear understanding we need to use sumtree.\n",
        "\n",
        "Then, we create a memory object that will contain our sumtree and data.\n",
        "\n",
        "Next, to sample a minibatch of size k, the range [0, total_priority] will be divided into k ranges. A value is uniformly sampled from each range.\n",
        "\n",
        "Finally, the transitions (experiences) that correspond to each of these sampled values are retrieved from the sumtree.\n",
        "\n",
        "![alt text](https://github.com/Machine-Learning-rc/Unimportant/blob/master/Screenshot%202020-07-19%20at%207.34.27%20PM.png?raw=true)\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "50vD2P10jCiH",
        "colab_type": "text"
      },
      "source": [
        "# Double DQN with a target network and Prioritized Experience Replay\n",
        "\n",
        "![alt text](https://github.com/Machine-Learning-rc/Unimportant/blob/master/Screenshot%202020-07-19%20at%201.23.53%20PM.png?raw=true)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "jjNMdLVgjENY",
        "colab_type": "text"
      },
      "source": [
        "# Implementing Double DQN with a target network and Prioritized Experience Replay"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "wWHR69eIc0i9",
        "colab_type": "text"
      },
      "source": [
        "Below code setups the environment required to run and record the game and also loads the required library."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "4fr-6_NCc2zX",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "!apt-get update > /dev/null 2>&1\n",
        "!apt-get install cmake > /dev/null 2>&1\n",
        "!pip install --upgrade setuptools 2>&1\n",
        "!pip install ez_setup > /dev/null 2>&1\n",
        "!pip install gym[atari] > /dev/null 2>&1\n",
        "!pip install gym pyvirtualdisplay > /dev/null 2>&1\n",
        "!apt-get install -y xvfb python-opengl ffmpeg > /dev/null 2>&1"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "py7ZChffc71N",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "import tensorflow as tf\n",
        "from tensorflow.keras.layers import Dense,Dropout,Conv2D, Flatten,MaxPooling2D ,Activation,Input\n",
        "from tensorflow.keras.models import Sequential,load_model,Model\n",
        "import gym\n",
        "import numpy as np\n",
        "import random\n",
        "from collections import deque\n",
        "from tensorflow.keras.utils import normalize as normal_values\n",
        "import cv2\n",
        "from gym import logger as gymlogger\n",
        "from gym.wrappers import Monitor\n",
        "gymlogger.set_level(40) #error only\n",
        "import matplotlib\n",
        "import matplotlib.pyplot as plt\n",
        "%matplotlib inline\n",
        "import math\n",
        "import glob\n",
        "import io\n",
        "import base64\n",
        "from IPython.display import HTML\n",
        "from IPython.display import clear_output\n",
        "from IPython import display as ipythondisplay "
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "1Qs6Psm1dLcd",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "from pyvirtualdisplay import Display\n",
        "display = Display(visible=0, size=(1400, 900))\n",
        "display.start()"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "PSC-XYIadS5p",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "\"\"\"\n",
        "Utility functions to enable video recording of gym environment and displaying it\n",
        "To enable video, just do \"env = wrap_env(env)\"\"\n",
        "\"\"\"\n",
        "\n",
        "def show_video():\n",
        "  mp4list = glob.glob('video/*.mp4')\n",
        "  if len(mp4list) > 0:\n",
        "    mp4 = mp4list[0]\n",
        "    video = io.open(mp4, 'r+b').read()\n",
        "    encoded = base64.b64encode(video)\n",
        "    ipythondisplay.display(HTML(data='''<video alt=\"test\" autoplay \n",
        "                loop controls style=\"height: 400px;\">\n",
        "                <source src=\"data:video/mp4;base64,{0}\" type=\"video/mp4\" />\n",
        "             </video>'''.format(encoded.decode('ascii'))))\n",
        "  else: \n",
        "    print(\"Could not find video\")\n",
        "    \n",
        "\n",
        "def wrap_env(env):\n",
        "  env = Monitor(env, './video', force=True)\n",
        "  return env"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "geN5sQm1dg5p",
        "colab_type": "text"
      },
      "source": [
        "This part ensures the reproducibility of the code below by using a random seed and setups the environment."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "7IHLaVZpdTdh",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "RANDOM_SEED=1\n",
        "N_EPISODES=500\n",
        "\n",
        "# random seed (reproduciblity)\n",
        "np.random.seed(RANDOM_SEED)\n",
        "tf.random.set_seed(RANDOM_SEED)\n",
        "\n",
        "# set the env\n",
        "env = (gym.make(\"KungFuMaster-v0\")) # env to import\n",
        "env.seed(RANDOM_SEED)\n",
        "env.reset() # reset to env "
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "mNdpj38Wd_A5",
        "colab_type": "text"
      },
      "source": [
        "Next we construct a SumTree and Memory object that will contain our sumtree and data."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "dy86mDChd-qu",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "class SumTree(object):\n",
        "\n",
        "  data_pointer = 0\n",
        "  \n",
        "  \"\"\"\n",
        "  Here we initialize the tree with all nodes = 0, and initialize the data with all values = 0\n",
        "  \"\"\"\n",
        "  def __init__(self, capacity):\n",
        "      self.capacity = capacity # Number of leaf nodes (final nodes) that contains experiences\n",
        "      \n",
        "      # Generate the tree with all nodes values = 0\n",
        "      # Remember we are in a binary node (each node has max 2 children) so 2x size of leaf (capacity) - 1 (root node)\n",
        "      # Parent nodes = capacity - 1\n",
        "      # Leaf nodes = capacity\n",
        "      self.tree = np.zeros(2 * capacity - 1)\n",
        "      \n",
        "      \"\"\" tree:\n",
        "          0\n",
        "          / \\\n",
        "        0   0\n",
        "        / \\ / \\\n",
        "      0  0 0  0  [Size: capacity] it's at this line that there is the priorities score (aka pi)\n",
        "      \"\"\"\n",
        "      \n",
        "      # Contains the experiences (so the size of data is capacity)\n",
        "      self.data = np.zeros(capacity, dtype=object)\n",
        "  \n",
        "  \n",
        "  \"\"\"\n",
        "  Here we add our priority score in the sumtree leaf and add the experience in data\n",
        "  \"\"\"\n",
        "  def add(self, priority, data):\n",
        "      # Look at what index we want to put the experience\n",
        "      tree_index = self.data_pointer + self.capacity - 1\n",
        "      \n",
        "      \"\"\" tree:\n",
        "          0\n",
        "          / \\\n",
        "        0   0\n",
        "        / \\ / \\\n",
        "tree_index  0 0  0  We fill the leaves from left to right\n",
        "      \"\"\"\n",
        "      \n",
        "      # Update data frame\n",
        "      self.data[self.data_pointer] = data\n",
        "      \n",
        "      # Update the leaf\n",
        "      self.update (tree_index, priority)\n",
        "      \n",
        "      # Add 1 to data_pointer\n",
        "      self.data_pointer += 1\n",
        "      \n",
        "      if self.data_pointer >= self.capacity:  # If we're above the capacity, you go back to first index (we overwrite)\n",
        "          self.data_pointer = 0\n",
        "          \n",
        "  \n",
        "  \"\"\"\n",
        "  Update the leaf priority score and propagate the change through tree\n",
        "  \"\"\"\n",
        "  def update(self, tree_index, priority):\n",
        "      # Change = new priority score - former priority score\n",
        "      change = priority - self.tree[tree_index]\n",
        "      self.tree[tree_index] = priority\n",
        "      \n",
        "      # then propagate the change through tree\n",
        "      while tree_index != 0:    # this method is faster than the recursive loop in the reference code\n",
        "          \n",
        "          \"\"\"\n",
        "          Here we want to access the line above\n",
        "          THE NUMBERS IN THIS TREE ARE THE INDEXES NOT THE PRIORITY VALUES\n",
        "          \n",
        "              0\n",
        "              / \\\n",
        "            1   2\n",
        "            / \\ / \\\n",
        "          3  4 5  [6] \n",
        "          \n",
        "          If we are in leaf at index 6, we updated the priority score\n",
        "          We need then to update index 2 node\n",
        "          So tree_index = (tree_index - 1) // 2\n",
        "          tree_index = (6-1)//2\n",
        "          tree_index = 2 (because // round the result)\n",
        "          \"\"\"\n",
        "          tree_index = (tree_index - 1) // 2\n",
        "          self.tree[tree_index] += change\n",
        "  \n",
        "  \n",
        "  \"\"\"\n",
        "  Here we get the leaf_index, priority value of that leaf and experience associated with that index\n",
        "  \"\"\"\n",
        "  def get_leaf(self, v):\n",
        "      \"\"\"\n",
        "      Tree structure and array storage:\n",
        "      Tree index:\n",
        "            0         -> storing priority sum\n",
        "          / \\\n",
        "        1     2\n",
        "        / \\   / \\\n",
        "      3   4 5   6    -> storing priority for experiences\n",
        "      Array type for storing:\n",
        "      [0,1,2,3,4,5,6]\n",
        "      \"\"\"\n",
        "      parent_index = 0\n",
        "      \n",
        "      while True: # the while loop is faster than the method in the reference code\n",
        "          left_child_index = 2 * parent_index + 1\n",
        "          right_child_index = left_child_index + 1\n",
        "          \n",
        "          # If we reach bottom, end the search\n",
        "          if left_child_index >= len(self.tree):\n",
        "              leaf_index = parent_index\n",
        "              break\n",
        "          \n",
        "          else: # downward search, always search for a higher priority node\n",
        "              \n",
        "              if v <= self.tree[left_child_index]:\n",
        "                  parent_index = left_child_index\n",
        "                  \n",
        "              else:\n",
        "                  v -= self.tree[left_child_index]\n",
        "                  parent_index = right_child_index\n",
        "          \n",
        "      data_index = leaf_index - self.capacity + 1\n",
        "\n",
        "      return leaf_index, self.tree[leaf_index], self.data[data_index]\n",
        "    \n",
        "  @property\n",
        "  def total_priority(self):\n",
        "    return self.tree[0] # Returns the root node"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2-iAhJGPmKvj",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "class Memory(object):  # stored as ( s, a, r, s_ ) in SumTree\n",
        "\n",
        "    PER_e = 0.01  # Hyperparameter that we use to avoid some experiences to have 0 probability of being taken\n",
        "    PER_a = 0.6  # Hyperparameter that we use to make a tradeoff between taking only exp with high priority and sampling randomly\n",
        "    PER_b = 0.4  # importance-sampling, from initial value increasing to 1\n",
        "    \n",
        "    PER_b_increment_per_sampling = 0.001\n",
        "    \n",
        "    absolute_error_upper = 1.  # clipped abs error\n",
        "\n",
        "    def __init__(self, capacity):\n",
        "        # Making the tree \n",
        "        \"\"\"\n",
        "        Remember that our tree is composed of a sum tree that contains the priority scores at his leaf\n",
        "        And also a data array\n",
        "        We don't use deque because it means that at each timestep our experiences change index by one.\n",
        "        We prefer to use a simple array and to overwrite when the memory is full.\n",
        "        \"\"\"\n",
        "        self.tree = SumTree(capacity)\n",
        "        \n",
        "    \"\"\"\n",
        "    Store a new experience in our tree\n",
        "    Each new experience have a score of max_prority (it will be then improved when we use this exp to train our DDQN)\n",
        "    \"\"\"\n",
        "    def store(self, experience):\n",
        "        # Find the max priority\n",
        "        max_priority = np.max(self.tree.tree[-self.tree.capacity:])\n",
        "        \n",
        "        # If the max priority = 0 we can't put priority = 0 since this exp will never have a chance to be selected\n",
        "        # So we use a minimum priority\n",
        "        if max_priority == 0:\n",
        "            max_priority = self.absolute_error_upper\n",
        "        \n",
        "        self.tree.add(max_priority, experience)   # set the max p for new p\n",
        "\n",
        "        \n",
        "    \"\"\"\n",
        "    - First, to sample a minibatch of k size, the range [0, priority_total] is / into k ranges.\n",
        "    - Then a value is uniformly sampled from each range\n",
        "    - We search in the sumtree, the experience where priority score correspond to sample values are retrieved from.\n",
        "    - Then, we calculate IS weights for each minibatch element\n",
        "    \"\"\"\n",
        "    def sample(self, n):\n",
        "        # Create a sample array that will contains the minibatch\n",
        "        memory_b = []\n",
        "        b_idx, b_ISWeights = np.empty((n,), dtype=np.int32), np.empty((n, 1), dtype=np.float32)\n",
        "      \n",
        "        # Calculate the priority segment\n",
        "        # Here, as explained in the paper, we divide the Range[0, ptotal] into n ranges\n",
        "        priority_segment = self.tree.total_priority / n       # priority segment\n",
        "\n",
        "        # Here we increasing the PER_b each time we sample a new minibatch\n",
        "        self.PER_b = np.min([1., self.PER_b + self.PER_b_increment_per_sampling])  # max = 1\n",
        "        \n",
        "        for i in range(n):\n",
        "            \"\"\"\n",
        "            A value is uniformly sample from each range\n",
        "            \"\"\"\n",
        "            a, b = priority_segment * i, priority_segment * (i + 1)\n",
        "            value = np.random.uniform(a, b)\n",
        "            \"\"\"\n",
        "            Experience that correspond to each value is retrieved\n",
        "            \"\"\"\n",
        "            index, priority, data = self.tree.get_leaf(value)\n",
        "            #P(j)\n",
        "            sampling_probabilities = priority / self.tree.total_priority\n",
        "            #  IS = (1/N * 1/P(i))**b /max wi == (N*P(i))**-b  /max wi\n",
        "            b_ISWeights[i] = np.power(n * sampling_probabilities, -self.PER_b)\n",
        "                                   \n",
        "            b_idx[i]= index\n",
        "            \n",
        "            experience = [data]\n",
        "            \n",
        "            memory_b.append(experience)\n",
        "\n",
        "        \n",
        "        b_ISWeights=b_ISWeights/tf.math.reduce_max(b_ISWeights)\n",
        "        \n",
        "        return b_idx,memory_b, b_ISWeights\n",
        "    \n",
        "    \"\"\"\n",
        "    Update the priorities on the tree\n",
        "    \"\"\"\n",
        "    def batch_update(self, tree_idx, abs_errors):\n",
        "        abs_errors += self.PER_e  # convert to abs and avoid 0\n",
        "        clipped_errors = np.minimum(abs_errors, self.absolute_error_upper)\n",
        "        ps = np.power(clipped_errors, self.PER_a)\n",
        "\n",
        "        for ti, p in zip(tree_idx, ps):\n",
        "            self.tree.update(ti, p)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1wAH57J0dmEJ",
        "colab_type": "text"
      },
      "source": [
        "Defining the DDQN Class.You can see that I have commented out few things like temperature_parameter .You can uncomment them if you can want to use Boltzmann policy.In this epsilon greedy works good. So I have used that."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Vc2Zv4o8nn-3",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "class DDQN:\n",
        "\n",
        "  def __init__(self, env,memory_size,path_1=None,path_2=None):\n",
        "    self.env=env #import env\n",
        "    self.memory=Memory(memory_size)\n",
        "    self.state_shape=70, 160, 4 # the state space\n",
        "    self.action_shape=env.action_space.n # the action space\n",
        "    self.gamma=[0.99] # decay rate of past observations\n",
        "    self.learning_rate= 0.001 # learning rate in deep learning\n",
        "    self.epsilon_initial_value=1.0 # initial value of epsilon\n",
        "    self.epsilon_current_value=1.0# current value of epsilon\n",
        "    self.epsilon_final_value=0.001 # final value of epsilon\n",
        "    self.nma=5 # No of Top actions to take while exploring \n",
        "    self.observing_episodes=10    #No of observations before training the training model\n",
        "    #self.temperature_parameter_initial_value=5.0 # initial value of epsilon\n",
        "    #self.temperature_parameter_current_value=5.0# current value of epsilon\n",
        "    #self.temperature_parameter_final_value=1.0 # final value of epsilon\n",
        "    self.observing_episodes_target_model=200\n",
        "    self.batch_size=64\n",
        "    if not path_1:\n",
        "      self.target_model=self._create_model()    #Target Model is model used to calculate target values\n",
        "      self.training_model=self._create_model()  #Training Model is model to predict q-values to be used.\n",
        "    else:\n",
        "      self.training_model=load_model(path_1)\n",
        "      self.target_model=load_model(path_2)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Ik4z-XFtofbe",
        "colab_type": "text"
      },
      "source": [
        "Creating a Neural Network Model."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "W9es6sqiogXI",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "  def _create_model(self):\n",
        "    ''' builds the model using keras'''\n",
        "    \n",
        "    model=Sequential()\n",
        "    model.add(Conv2D(256, (8, 8), padding='same',strides=(4, 4),input_shape=(self.state_shape))\n",
        "    model.add(MaxPooling2D(pool_size=(2,2),padding='same'))\n",
        "    model.add(Activation('relu'))\n",
        "    model.add(Conv2D(64, (4, 4),strides=(2, 2),  padding='same'))\n",
        "    model.add(MaxPooling2D(pool_size=(2,2),padding='same'))\n",
        "    model.add(Activation('relu'))\n",
        "    model.add(Conv2D(32, (3, 3),strides=(1, 1),  padding='same'))\n",
        "    model.add(MaxPooling2D(pool_size=(2,2),padding='same'))\n",
        "    model.add(Activation('relu'))\n",
        "    model.add(Flatten())\n",
        "    model.add(Dense(512))\n",
        "    model.add(Activation('relu'))\n",
        "    model.add(Dense(14))\n",
        "    model.add(Activation('softmax'))\n",
        "    model.compile(loss='mse',optimizer=tf.keras.optimizers.Adam(learning_rate=1e-4))\n",
        "    return model"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vNXwCByQotKE",
        "colab_type": "text"
      },
      "source": [
        "Action Selection\n",
        "The get_action method guides out action choice. Initially, when training begins we use exploration policy but later we do exploitation.\n",
        "\n",
        "You can uncomment the commented lines to use Boltzmann exploration policy instead of epsilon greedy policy."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "5oi8Ur9rouSg",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "  def get_action(self, state):\n",
        "        '''samples the next action based on the E-greedy policy'''\n",
        "\n",
        "        x=random.random()\n",
        "        if x < self.epsilon_current_value:                                    #Exlporation\n",
        "          #q_values=((self.target_model.predict(state))[0])**(1/self.temperature_parameter_current_value)  #This is the step where we use Boltzmann exploration policy\n",
        "          #top_actions=q_values.argsort()[-self.nma:][::-1]\n",
        "          #action=random.choice(top_actions)\n",
        "          action=random.choice(list(range(14)))\n",
        "\n",
        "        else:\n",
        "          #q_values=((self.model.predict(state))**(1/(self.temperature_parameter_current_value)))[0] #Exploitation\n",
        "          q_values=(self.training_model.predict(state))[0]\n",
        "          max_Q = np.argmax(q_values)\n",
        "          action = max_Q\n",
        "        return action"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "dJokVaFipDr0",
        "colab_type": "text"
      },
      "source": [
        "This is the preprocessing we do to the image we obtained by interacting with the environment. Here I have done grayscaling and also cropped the image to remove game scores and area which I found was not necessary to train the agent. This speeds up the training process."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "7iX6AI1BpHtT",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "  def get_frame(self,frame):\n",
        "    frame=frame[95:-45,:]\n",
        "    frame=cv2.cvtColor(frame, cv2.COLOR_RGB2GRAY)\n",
        "    frame=(frame-frame.mean())/frame.std()\n",
        "    return frame"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "uItQwyAHqBOO",
        "colab_type": "text"
      },
      "source": [
        "Updating the training_model\n",
        "\n",
        "The update_training_model method updates the training model weights. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "XTbhP8p6qEiK",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "  def update_training_model(self):\n",
        "\n",
        "    '''\n",
        "    Updates the policy network using the NN model.\n",
        "    '''\n",
        "\n",
        "\n",
        "    tree_idx, batch, ISWeights_mb = self.memory.sample(self.batch_size)\n",
        "    \n",
        "    states_mb=np.zeros((self.batch_size,self.state_shape))\n",
        "    targets = np.zeros((self.batch_size,self.action_shape))\n",
        "    absolute_errors=np.zeros((self.batch_size,1))\n",
        "\n",
        "    for i in range(self.batch_size):\n",
        "      state=batch[i][0][0]\n",
        "      states_mb[i]=state\n",
        "      preds_=self.training_model.predict(state)\n",
        "      targets[i]=preds_\n",
        "\n",
        "      reward=(batch[i][0][2])\n",
        "      \n",
        "      terminal=batch[i][0][4]\n",
        "\n",
        "     \n",
        "      action=batch[i][0][1]\n",
        "      if terminal:  # If we are in a terminal state, only equals reward\n",
        "        targets[i, action] = np.asarray(reward)\n",
        "      else:\n",
        "        next_state=batch[i][0][3]\n",
        "        preds_next_state_target_model=self.target_model.predict(next_state)[0,action]\n",
        "        targets[i, action] =  np.asarray(reward) + np.asarray(self.gamma)*np.asarray(preds_next_state_target_model)   # Take the Qtarget for action a'\n",
        "      \n",
        "      absolute_errors[i]=np.abs(np.sum(targets[i]-preds_,axis=1))\n",
        "  \n",
        "      # Update priority\n",
        "      absolute_errors=absolute_errors/np.amax(absolute_errors)\n",
        "      self.memory.batch_update(tree_idx, absolute_errors)\n",
        "\n",
        "      optimizer = tf.keras.optimizers.Adam(learning_rate=self.learning_rate)\n",
        "      def train_step(states, targets,ISWeights):\n",
        "        with tf.GradientTape() as tape:\n",
        "          preds= (self.training_model)(states,training=True)  #This is the 𝑄@(𝑠,𝑎)\n",
        "          loss= ISWeights*(targets-preds)                 \n",
        "          \n",
        "        grads = tape.gradient(loss,self.training_model.trainable_variables)\n",
        "        optimizer.apply_gradients(zip(grads, self.training_model.trainable_variables))\n",
        "      train_step(states_mb,targets,ISWeights_mb)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "xVi3FsdaqkU7",
        "colab_type": "text"
      },
      "source": [
        "Updating the target_model\n",
        "\n",
        "The update_target_model method sets the target model weights to training model weights."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "oq7dlYO0q3Rf",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "  def update_target_model(self):\n",
        "    self.target_model.set_weights(self.training_model.get_weights())"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "uOThRxPNrhMZ",
        "colab_type": "text"
      },
      "source": [
        "Training the model\n",
        "\n",
        "This method creates a training environment for the model. Iterating through a set number of episodes, it uses the model to sample actions and play them. When such a timestep ends, the model is using the observations to update the policy.\n",
        "\n",
        "We know that in a dynamic game we cannot predict action based on 1 observation(which is 1 frame of the game in this case) so we will use a stack of 4 frames to predict the output.\n",
        "\n",
        "We can also clip the rewards to help model learn faster."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "NyCRjAYWrhj7",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "  def train(self, episodes):\n",
        "    '''\n",
        "    train the model\n",
        "    episodes - number of training iterations\n",
        "    ''' \n",
        "    env=self.env\n",
        "    for episode in range(episodes):\n",
        "      # each episode is a new game env\n",
        "      state=env.reset()\n",
        "      done=False\n",
        "      state= self.get_frame(state)\n",
        "      stacked_frame=np.stack((state,state,state,state),axis=2)\n",
        "      stacked_frame=stacked_frame.reshape(1,stacked_frame.shape[0],stacked_frame.shape[1],stacked_frame.shape[2])\n",
        "      state=stacked_frame\n",
        "      episode_reward=0 #record episode reward\n",
        "      print(\"Episode Started\")\n",
        "      while not done:\n",
        "        # play an action and record the game state & reward per episode\n",
        "        action=self.get_action(state)\n",
        "        print(\"Episode Going On.\"+\"\\n\"+\"Action taken:\",action)\n",
        "        next_state, reward, done, _=env.step(action)\n",
        "        next_state=self.get_frame(next_state)\n",
        "        next_state_ = next_state.reshape(1,next_state.shape[0],next_state.shape[1],1)\n",
        "        stacked_frames_1 = np.append(next_state_, stacked_frame[:, :, :, :3], axis=3)\n",
        "        next_state=stacked_frames_1\n",
        "        experience = state, action, reward, next_state, 1*done\n",
        "        self.memory.store(experience)\n",
        "        state=next_state\n",
        "        episode_reward+=reward\n",
        "      print(\"Episode:{}  reward:{}\".format(episode,episode_reward))\n",
        "      print(\"Episode Ended\")\n",
        "      if episode%self.observing_episodes==0 and episode!=0:\n",
        "        self.update_training_model()\n",
        "      if episode%self.observing_episodes_target_model==0 and episode!=0:\n",
        "        self.update_target_model()\n",
        "        self.target_model.save('target_model_{}.h5'.format(episode))\n",
        "      if episode%500==0 and episode!=0:\n",
        "        self.training_model.save('training_model_{}.h5'.format(episode))\n",
        "      if self.epsilon_current_value > self.epsilon_final_value:\n",
        "        self.epsilon_current_value=self.epsilon_current_value-(self.epsilon_initial_value-self.epsilon_final_value)/1000\n",
        "        print('Current Epsilon Value:',self.epsilon_current_value)\n",
        "      #if self.temperature_parameter_current_value > self.temperature_parameter_final_value:\n",
        "        #self.temperature_parameter_current_value=self.temperature_parameter_current_value-(self.temperature_parameter_initial_value-self.temperature_parameter_final_value)/1000"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "xFogpNR1sGt8",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "memory_size=10000\n",
        "no_of_episodes=2000\n",
        "\n",
        "Agent=DDQN(env,memory_size)\n",
        "Agent.train(no_of_episodes)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "hAqoKml5sXNH",
        "colab_type": "text"
      },
      "source": [
        "With the help of below code we run our algorithm and see the success of it.With the help of below code we run our algorithm and see the success of it."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wgm5-bIUslUI",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "class tester:\n",
        "\n",
        "  def __init__(self,path):\n",
        "    self.model=load_model(path)\n",
        "      \n",
        "  \n",
        "  def get_action(self, state):\n",
        "        '''samples the next action based on the E-greedy policy'''\n",
        "        q_values=(self.model.predict(state))[0]    #Exploitation\n",
        "        action = np.argmax(q_values)\n",
        "        return action\n",
        "  \n",
        "  def get_frame(self,frame):\n",
        "    frame=frame[95:-45,:]\n",
        "    frame=cv2.cvtColor(frame, cv2.COLOR_RGB2GRAY)\n",
        "    frame=(frame-frame.mean())/frame.std()\n",
        "    return frame"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "OlMFpbl0s-Gv",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "env=(wrap_env(gym.make(\"KungFuMaster-v0\")))\n",
        "state=env.reset()\n",
        "done=False\n",
        "test=tester(\"Actor.h5\")\n",
        "state=test.get_frame(state)\n",
        "stacked_frames = np.stack((state,state,state,state),axis=2)\n",
        "stacked_frames = stacked_frames.reshape(1,stacked_frames.shape[0],stacked_frames.shape[1],stacked_frames.shape[2]) \n",
        "state_=stacked_frames\n",
        "while True:\n",
        "  env.render('ipython')\n",
        "  action = test.get_action(state_)\n",
        "  next_state, reward, done, _=env.step(action)\n",
        "  print(action,reward)\n",
        "  next_state=test.get_frame(next_state)\n",
        "  next_state_ = next_state.reshape(1,next_state.shape[0],next_state.shape[1],1)\n",
        "  stacked_frames_1 = np.append(next_state_, stacked_frames[:, :, :, :3], axis=3)\n",
        "  next_state_=stacked_frames_1\n",
        "  state_=next_state_\n",
        "  if done:\n",
        "    break\n",
        "env.close()\n",
        "show_video()"
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}