Deep_Q-Network.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Deep Q-Network"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## From RL to Deep RL\n",
    "So far, we have solved many problem of our reinforcement learning problems, using solution methods that represent the action values in a small table. Earlier in the nanodegree, we referred to this table as a **Q-table**.\n",
    "\n",
    "In the video below, **Kelvin Lwin** will introduce us to the idea of using neural networks to expand the size of the problems that we can solve with reinforcement learning. This context is useful preparation for exploring hte details behind the Deep Q-Learning algorithm later in this lesson!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* DeepRL : Using nonlinear function approximators to calculate the value actions based directly on the observation from the environment. We represent this as Deep Neural network.\n",
    "\n",
    "#### Stabilizing Deep Reinforcement Learning\n",
    "---\n",
    "As we'll learn in this lesson, the Deep Q-Learning algorithm represents the optimal action value function $q_*$ as a neural network (instead of table).\n",
    "\n",
    "* Unfortunately, reinforcement learning is __notoriously unstable__ when neural networks are used to represent the action values. In this lesson, we will learn all about the Deep Q-Learning algorithm, which addressed these instabilities by using __two key features:__\n",
    "    * Experience Replay\n",
    "    * Fixed Q-Targets\n",
    "    \n",
    "    \n",
    "### Deep Q-Networks\n",
    "* _HOW IT WORKS_\n",
    "    * A deep neural network that acts as a function approximator.\n",
    "    * Input : Raw pixels and it outputs the vector of actions.\n",
    "    * Atari games are displayed at a resolution of 210 by 160 pixels, with 128 possible colors for each pixel. This is still technically a discrete state space but very large to process as is.\n",
    "    * Deepmind reduce this image to 84 by 84 and grayscale.(square to optimize operation in GPU).\n",
    "    * To give it sequence of frame they(deepmind) stack 4 frame at a time.Resulting final state size (84 by 84 by 4).\n",
    "    * On the output side unlike a traditional reinforcement learning setup where only one Q value is produced at a time, __The Q network is designed to produce a Q value for every possible action in a single forward pass.__\n",
    "    * Without this, we would have to run the network individually for every action.\n",
    "    * Instead we could simply use this vector to take an action, either stochastically, or by choosing the one with maximum value.\n",
    "    \n",
    "* TRAINING SUCH NETWORK REQUIRES A LOT OF DATA, BUT EVEN THEN, IT IS NOT GUARANTEED TO CONVERGE ON THE OPTIMAL VALUE FUNCTION. **IN FACT THRER ARE SITUATIONS WHERE THE NETWORK WEIGHTS CAN OSCILLATE OR DIVERGE, due to high correlation between action and states.**\n",
    "* This can result in a very unstabke and ineffectively policy.\n",
    "    * Experience Replay\n",
    "    * Fixed Q-Targets\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Experience Replay\n",
    "* The idea of experience relay and its application to training neural network isn't new.\n",
    "* It was originally proposed to make more efficient use of observed experiences.\n",
    "* Consider the basic online Q-Learning algorithm where we interact with environment and at each time step, we obtain a state action reward next state tuple.$(S_t,A_t,R_{t+1},S_{t+1})$, we learn from it and __discard__ it.\n",
    "* Moving on to the next tuple in the following timestep.\n",
    "* We could possibly can learn more from these experienced tuples if we store them somewhere.\n",
    "* Moreover, some states. are pretty rare to come by and some action can be pretty costly, so it would be nice to **recall** such experiences.\n",
    "* That is what exactly what a replay buffer allows us to do.\n",
    "\n",
    "### Replay Buffer\n",
    "* We store each experienced tuple in this buffer as we are interacting with the environment and then sample a small batch of tuples from it in order to learn.\n",
    "* As a result, we are able to learn from individual tuples multiple times, recall rare occurrences, and in general make better use of our experience.\n",
    "\n",
    "\n",
    "<br>**Another Problem that replay buffer solves.**\n",
    "* This what DQN takes advantage of.\n",
    "* If you think about the experiences being obtained, we realize that every action __AT__ affects the next state __ST__ in some way, which means that a __sequence of experienced tuples can be highly correlated__.\n",
    "* A naive Q-Learning approach that learns from each of these experiences in sequential order runs the risk of getting swayed by the effect of this correlation.\n",
    "* With experience replay, can sample form this buffer at random.\n",
    "* It doesn't have to be in the same sequence as we stored the tuples.\n",
    "* This helps break the correlation and ultimately prevents action values from oscillating or diverging catastrophically.\n",
    "\n",
    "### Example to show why we need to break correlation between subsequent experience tuple\n",
    "\n",
    "#### Tennis Example:\n",
    "* Practicing forehand, learning to play tennis.\n",
    "* More confident with forehand shot than backhand.\n",
    "* I hit the ball __straight__ so ball comes straight back to my forehand.\n",
    "\n",
    "* Now, if I were an online Q-learning agent learning to play, this is what I might pick up.\n",
    "* When the ball comes to my right, should hit with my forehand less certainly at first but with increasing confident as I repeatedly hit the ball.\n",
    "* I'm learning to play forehand pretty well **but not exploring rest of the state space**\n",
    "* This could be addressed by _Epsilon-greedy policy action randomly with small chances._\n",
    "* So I try different combinations of states and actions and sometimes I make mistakes, but I eventually figure out the best overall policy.\n",
    "* Use a forehand shot when the ball comes to my right and a backhand when it comes to my left.\n",
    "\n",
    "* __THIS WORKS FINE WITH SIMPLIFIED STATE SPACE WITH JUST two Discrete states__\n",
    "\n",
    "\n",
    "#### Continuous state space -- Problem\n",
    "* But when we consider a continuous state space things can fall apart. Let's see how.\n",
    "* First the ball can actually come anywhere between the extreme left and extreme right.\n",
    "* If I discretized this range into buckets I will have too many buckets(too many possibilites).\n",
    "* What if I end up learning a policy with __holes__ in it.\n",
    "* States or situation that we may not have visited during practice.\n",
    "* Instead it makes more sense to use a function approximator like alinear combination of (RBF kernels or a Q-network) that can generalize my learning across the space.\n",
    "* Now, every time the ball comes to my right and I successfully hit a forehand shot, my value function changes slightly.\n",
    "\n",
    "* What happens when I learn while playing(__processing each experience tuple in order__)\n",
    "* For instance, if my forehand shot is fairly  straight, I likely get back the ball around the same spot.\n",
    "* __This produces a state very similar to the previous one, so I use my forehand again and if it is successful it reinforces my belief that forehand is a good choice__\n",
    "* I can easily get trapped in this cycle.\n",
    "* Ultimately, if I don't see too many examples of the ball coming to my left for a while, value of forehand shot become greater than backhand across the entire state space.\n",
    "* __My policy would be then be to choose forehand regardless of where I see the ball coming.__\n",
    "\n",
    "\n",
    "### Fix it\n",
    "* First thing I should do is stop learning while practicing.\n",
    "* This time is best spend in trying out different shots playing little randomly and thus exploring the state space.\n",
    "* It becomes important to remember my interactions, what shot well in situations, etc.\n",
    "* When I take a break or when I am back home or resting, that's the good time to recall these experiences and learn from them.\n",
    "\n",
    "* The main advantages is that now I have a more comprehensive set of examples.\n",
    "* I can call random experience tuple from buffer and learn different shot in different region.\n",
    "* After this with this __learn experienced__ I will again play and __collect more experience tuple__ and learn from them in batches.\n",
    "* __Experience replay__ can help us to learn more robust policy, one that is not affected by the inherent correlation present in the sequence of observed experience tuples.\n",
    "\n",
    "\n",
    "### Experience Replay\n",
    "* Reinforcement learning ->  Supervised Learning\n",
    "* Prioritized Experience Replay\n",
    "\n",
    "\n",
    "### Summary\n",
    "When the agent interacts with the environment, the sequence of experienced tuples can be highly correlated. The naive Q-learning algorithm that learns from each of these experience tuples in sequential order runs the risk of getting swayed by the effects of this correlation. By instead keeping track of a **replay buffer** and using **experience replay** to sample from the buffer at random, we can prevent action values from oscillating or diverging catastrophically.\n",
    "\n",
    "The **replay buffer** contains a collection of experience tuples ($S, A, R,S^{`}$). The tuples are gradually added to the buffer as we are interacting with the environment.\n",
    "\n",
    "The act of sampling a small batch of tuples from the replay buffer in order to learn is known as __experience replay__. In addition to breaking harmful correlations, experience replay allows us to learn more from individual tuples multiple times, recall rare occurrences, and in general make better use of our experience.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Fixed Q-Targets\n",
    "* Experience replay helps us address one type of correlation.\n",
    "    * That is between consecutive experience tuples.\n",
    "* There is another kind of correlation that Q-learning is susceptible to.\n",
    "\n",
    "### Q-learning update\n",
    "$\\Delta w = \\alpha (R + \\gamma max_{a} q^{`}(S^{`},a,w^{-}) - q^{`}(S,A,w)) dw q^{`}(S,A,w)$\n",
    "\n",
    "* TD error: $(R + \\gamma max_{a} q^{`}(S^{`},a,w^{-}) - q^{`}(S,A,w))$\n",
    "* TD target: $R + \\gamma max_{a} q^{`}(S^{`},a,w^{-})$\n",
    "* Old value: $q^{`}(S,A,w)$\n",
    "\n",
    "where $w^{-}$ are the weights of a sperate target network that are not changed during learning step, and $(S,A,R,S^{`})$ is an experience tuple.\n",
    "\n",
    "<br>$ J(w) = E_{\\pi}[(q_\\pi(S,A) - q^{`}(S,A,w))^2]$\n",
    "<br>$d J(w) = -2(q_\\pi(S,A)- q^{`}(S,A,w))d q^{`}(S,A,w)$\n",
    "<br>$dw = - \\alpha \\frac{1}{2} dJ(w)$\n",
    "<br>$= \\alpha(q_\\pi(S,A) - q^{`}(S,A,w))dq^{`}(S,A,w)$\n",
    "<br>$dw  = \\alpha (R+\\gamma max_{a}q^{`}(S^{`},a,w)- q^{`}(S,A,w))dq^{`}(S,A,w)$\n",
    "\n",
    "* The main idea of introducing fixed Q targets is both **labels** and **predicted values** are function of **SAME** weights.\n",
    "\n",
    "* All the Q values are intrinsically tied together through the function parameters.\n",
    "* Dosen't expereience replay take care of this problem?\n",
    "    * Well, it addresses a similar but slightly different issue.\n",
    "        * There we broke the correlation effects between consecutive tuples by sampling them randomly out of order.\n",
    "* Here, the correlation between the target and the parameters we are changing.\n",
    "\n",
    "### Fixed Target\n",
    "$dw  = \\alpha (R+\\gamma max_{a}q^{`}(S^{`},a,w^{-})- q^{`}(S,A,w))dq^{`}(S,A,w)$\n",
    "* The fixed parameters indicated by a w minus are basically a copy of w that we don't change during the learning step.\n",
    "* In practice, we copied w into w minus, use to generate targets while changing w for a certain number of learning steps.\n",
    "* Then, we update w minus with the latest w, again, learn for a number of steps and so on.\n",
    "* __This decouples the target from the parameters, makes the learning algorithm much more stable, and less likely to diverge or fall into oscillations.__\n",
    "\n",
    "## Summary \n",
    "In Q-Learning, we **update a guess with a guess**, and this can potentially lead to harmful correlations. To avoid this, we can update the parameters $w$ in the network $q^{`}$ to better approximate the action value corresponding to state $S$ and action $A$ with following update rule:\n",
    "$ \\Delta w = \\alpha (R + \\gamma max_{a} q^{`}(S^{`},a,w^{-}) - q^{`}(S,A,w)) dw q^{`}(S,A,w)$\n",
    "\n",
    "where $w^-$ are the weights of a separate target network that are not changed during the learning step, and $(S,A,R,S^{`})$ is an experience tuple."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## DQN Network Paper\n",
    "* Neural fitted Q-iteration -- Search about it\n",
    "\n",
    "### Methods\n",
    "**Preprocessing**. Working directly with raw Atari 2600 frames, which are $210 \\times 160$ pixel images with a 128 colour palette, can be demanding in terms of computation and memory requirements. We apply a basic preprocessing step aimed reducing the inut dimensionality and dealing with some aretefact of Atari 2600 emulator. _First, to encode a single frame we take the maximum value for each pixel colour value over the frame being encoded and the previous frame. This was necessary to remove the flickering that is present in games where some objects appear only in even frames while other objects appear only in odd frames, an artefact caused by limited number of *sprites* Atari 2600 can display at once_. Second, we then extract the Y channel, also known as luminance, from the RGB frame and rescale it to $84 \\times 84$. The function $\\phi$ from algorithm 1 described below applies this preprocessing to the m most recent frames and stacks them to produce the input to the Q-function in which m =4, although algorithm is robust to different values of m(example 3,5).\n",
    "\n",
    "**Model architecture** There are several possible ways of parameterizing Q using a neural network.Because Q maps history-actions pairs to scalar estimates of their Q-values of each action,the history and the action have been used as inputs to the neural network by some previous approaches.**The main drawback of this type of architecture is that a separate forward pass is required to compute the Q-value for each actionm resulting in a cost that scales linearly woth the number of actions**.\n",
    "\n",
    "\n",
    "We instead use an architecture is which there is a seperate output unit for each possible action, and only the state representation is an input ot the neural network. The outputs corresponding to the predicted Q-values of the individual actions for the input state. __The main advantage of this type of architecuture is the ability to compute Q-values for all possible actions in a given state with single pass(forward pass)__.\n",
    "    The exact architecture, shown(figure).The input to the neural network consists of an $84 \\times 84 \\times 4$ image produced by the preprocessing map $\\phi$. \n",
    "<br>**First hidden layer**:The first hidden layer convolves 32 filters of $8 \\times 8$ with stride of 4 with the ReLU activation.\n",
    "<br>**Second hidden layer**: Convolves 64 filters of $4 \\times 4 $ with stride of 2, again ReLU activation.\n",
    "<br>**Third hidden layer** Convolves 64 filters of $3 \\times 3$ with stride of 1 followed by ReLU activation.\n",
    "<br>**Final hidden layer** is a fully connected layer and consists of 512 nodes with ReLU activation. and number of valid actions varied between 4 and 18 on the game we considered.\n",
    "\n",
    "**Trainig details**: We performed experiments on 49 Atari games 2600 games where results were available for all other comparable methods.A different network was trained on each game: the same network architecture, learning algorithm and hyperparameter setting were used across all games, showing our approach is robust enough to work on a variety of games while incorporating only minimal prior knoweldge.\n",
    "\n",
    "#### Reward clipping \n",
    "Changes in reward system structure of games during training only. As the scale of scores varies greatly from game to game, we **clipped all positive rewards at 1 and all negative reward at -1**, leaving 0 rewards unchanged. Clipping rewards in this manner limits the scale of the error derivatives and makes it wasier to use the same learning rate across multiple games. __At the same time, it could affect the performance of our agent since it cannot differenitate between rewards of different magnitude__. For games where there is a life counter, the Atari 2600 emulator also sends the number of lives left in the game, which is then used to mark the end of the episode.\n",
    "\n",
    "#### OPTIMIZATION\n",
    "In these experiments, we used RMSProp algorithm with minibatches of size of 32. The behaviour policy during training is epsilon greedy policy with epsilon __annealed linerality__(decaying) from 1.0 to 0.1 over the first million frames, and fixed at 0.1 thereafter. We trained for a total of 50 million frames __(that is, around 38 days of game experience in total)__ and used a replay memory of 1 million most recent frame."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7.0"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#convolution formula\n",
    "#lout  =floor[lin - k_s + 2P/s +1]\n",
    "(84 -8)/4 +1 ## 20*20*32\n",
    "(20-4)/2 +1 ## 9*9*64\n",
    "(9-3)/1 +1  ## 7*7*64\n",
    "## flatten \n",
    "#(batch_size,3136) * (3136,512) hidden layer weight dimensions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### DQN Network -- implementation\n",
    "\n",
    "### Necessary Packages\n",
    "```python\n",
    "import gym\n",
    "!pip3 install box2d\n",
    "import random\n",
    "import torch\n",
    "import numpy as np\n",
    "from collections import deque\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "\n",
    "!python -m pip install pyvirtualdisplay\n",
    "from pyvirtualdisplay import Display\n",
    "display = Display(visible=0, size=(1400, 900))\n",
    "display.start()\n",
    "\n",
    "is_ipython = 'inline' in plt.get_backend()\n",
    "if is_ipython:\n",
    "    from IPython import display\n",
    "\n",
    "plt.ion()\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Instantiate the Environment and Agent\n",
    "```python\n",
    "env = gym.make('LunarLander-v2')\n",
    "env.seed(0)\n",
    "print(\"State shape : \", env.observation_space.shape)\n",
    "print(\"Number of actions : \", env.action_space.n)\n",
    "```\n",
    "\n",
    "\n",
    "Before running the next code cell, familiarize ourself with code in **Steps 2** and **Steps 3** of this notebook, along with the code in `dqn_agent.py` and `model.py`. Once we have an understanding of how the different files work together,\n",
    "- Define  a neural network architecture in `model.py` that maps states to action values. This file mostly empty - its's up to us to define our own deep Q-network!\n",
    "- Finish the `learn` method in the `Agent` class in `dqn_agent.py`. The sampled batch of experience tuples is already provided for us; we need only use the local and target Q-networks to compute the loss, before taking a steps towards minimizing the loss.\n",
    "\n",
    "Once we have completed the code in `dqn_agent.py` and `model.py`, run the code cell below. (_If we end up needing to make multiple changes and get unexpected behaviour, please restart the kernel and run the cell for the beginning of the notebook!_)\n",
    "\n",
    "_(Note that there are many ways to train the agent and solve the exercise, and the \"solution\" is one way of approaching the problem, to yield a trained agent)_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Model Architecture"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import torch \n",
    "import torch.nn as nn\n",
    "import torch.nn.functional as F\n",
    "\n",
    "\n",
    "class QNetwork(nn.Module):\n",
    "    \"\"\" Actor (Policy) Model.\"\"\"\n",
    "    def __init__(self, state_size,action_size, seed, fc1_unit=64,\n",
    "                 fc2_unit = 64):\n",
    "        \"\"\"\n",
    "        Initialize parameters and build model.\n",
    "        Params\n",
    "        =======\n",
    "            state_size (int): Dimension of each state\n",
    "            action_size (int): Dimension of each action\n",
    "            seed (int): Random seed\n",
    "            fc1_unit (int): Number of nodes in first hidden layer\n",
    "            fc2_unit (int): Number of nodes in second hidden layer\n",
    "        \"\"\"\n",
    "        super(QNetwork,self).__init__() ## calls __init__ method of nn.Module class\n",
    "        self.seed = torch.manmual_seed(seed)\n",
    "        self.fc1= nn.Linear(state_size,fc1_unit)\n",
    "        seed.fc2 = nn.Linear(fc1_unit,fc2_unit)\n",
    "        seed.fc3 = nn.Linear(fc2_unit,action_size)\n",
    "        \n",
    "    def forward(self,x):\n",
    "        # x = state\n",
    "        \"\"\"\n",
    "        Build a network that maps state -> action values.\n",
    "        \"\"\"\n",
    "        x = F.relu(self.fc1(x))\n",
    "        x = F.relu(self.fc2(x))\n",
    "        return self.fc3(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# dqn Agent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import random \n",
    "from collections import namedtuple, deque \n",
    "\n",
    "##Importing the model (function approximator for Q-table)\n",
    "from model import QNetwork\n",
    "\n",
    "import torch\n",
    "import torch.nn.functional as F\n",
    "import torch.optim as optim\n",
    "\n",
    "BUFFER_SIZE = int(1e5)  #replay buffer size\n",
    "BATCH_SIZE = 64         # minibatch size\n",
    "GAMMA = 0.99            # discount factor\n",
    "TAU = 1e-3              # for soft update of target parameters\n",
    "LR = 5e-4               # learning rate\n",
    "UPDATE_EVERY = 4        # how often to update the network\n",
    "\n",
    "device = torch.device(\"cuda:0\" if torch.cuda.is_available() else \"cpu\")\n",
    "\n",
    "class Agent():\n",
    "    \"\"\"Interacts with and learns form environment.\"\"\"\n",
    "    \n",
    "    def __init__(self, state_size, action_size, seed):\n",
    "        \"\"\"Initialize an Agent object.\n",
    "        \n",
    "        Params\n",
    "        =======\n",
    "            state_size (int): dimension of each state\n",
    "            action_size (int): dimension of each action\n",
    "            seed (int): random seed\n",
    "        \"\"\"\n",
    "        \n",
    "        self.state_size = state_size\n",
    "        self.action_size = action_size\n",
    "        self.seed = random.seed(seed)\n",
    "        \n",
    "        \n",
    "        #Q- Network\n",
    "        self.qnetwork_local = QNetwork(state_size, action_size, seed).to(device)\n",
    "        self.qnetwork_target = QNetwork(state_size, action_size, seed).to(device)\n",
    "        \n",
    "        self.optimizer = optim.Adam(self.qnetwork_local.parameters(),lr=LR)\n",
    "        \n",
    "        # Replay memory \n",
    "        self.memory = ReplayBuffer(action_size, BUFFER_SIZE,BATCH_SIZE,seed)\n",
    "        # Initialize time step (for updating every UPDATE_EVERY steps)\n",
    "        self.t_step = 0\n",
    "        \n",
    "    def step(self, state, action, reward, next_step, done):\n",
    "        # Save experience in replay memory\n",
    "        self.memory.add(state, action, reward, next_step, done)\n",
    "\n",
    "        # Learn every UPDATE_EVERY time steps.\n",
    "        self.t_step = (self.t_step+1)% UPDATE_EVERY\n",
    "        if self.t_step == 0:\n",
    "            # If enough samples are available in memory, get radom subset and learn\n",
    "\n",
    "            if len(self.memory)>BATCH_SIZE:\n",
    "                experience = self.memory.sample()\n",
    "                self.learn(experience, GAMMA)\n",
    "    def act(self, state, eps = 0):\n",
    "        \"\"\"Returns action for given state as per current policy\n",
    "\n",
    "        Params\n",
    "        =======\n",
    "            state (array_like): current state\n",
    "            eps (float): epsilon, for epsilon-greedy action selection\n",
    "\n",
    "        \"\"\"\n",
    "        state = torch.from_numpy(state).float().unsqueeze(0).to(device)\n",
    "        self.qnetwork_local.eval()\n",
    "        with torch.no_grad():\n",
    "            action_values = self.qnetwork_local(state)\n",
    "        self.qnetwork_local.train()\n",
    "\n",
    "        #Epsilon -greedy action selction\n",
    "        if random.random() > eps:\n",
    "            return np.argmax(action_values.cpu().data.numpy())\n",
    "        else:\n",
    "            return random.choice(np.arange(self.action_size))\n",
    "            \n",
    "    def learn(self, experiences, gamma):\n",
    "        \"\"\"Update value parameters using given batch of experience tuples.\n",
    "\n",
    "        Params\n",
    "        =======\n",
    "\n",
    "            experiences (Tuple[torch.Variable]): tuple of (s, a, r, s', done) tuples\n",
    "\n",
    "            gamma (float): discount factor\n",
    "        \"\"\"\n",
    "        states, actions, rewards, next_state, dones = experiences\n",
    "        ## TODO: compute and minimize the loss\n",
    "        criterion = torch.nn.MSELoss()\n",
    "        self.qnetwork_local.train()\n",
    "        self.qnetwork_target.eval()\n",
    "        #shape of output from the model (batch_size,action_dim) = (64,4)\n",
    "        predicted_targets = self.qnetwork_local(states).gather(1,actions)\n",
    "    \n",
    "        with torch.no_grad():\n",
    "            labels_next = self.qnetwork_target(next_states).detach().max(1)[0].unsqueeze(1)\n",
    "\n",
    "        # .detach() ->  Returns a new Tensor, detached from the current graph.\n",
    "        labels = rewards + (gamma* labels_next*(1-dones))\n",
    "        \n",
    "        loss = criterion(predicted_targets,labels).to(device)\n",
    "        self.optimizer.zero_grad()\n",
    "        loss.backward()\n",
    "        self.optimizer.step()\n",
    "\n",
    "        # ------------------- update target network ------------------- #\n",
    "        self.soft_update(self.qnetwork_local,self.qnetwork_target,TAU)\n",
    "            \n",
    "    def soft_update(self, local_model, target_model, tau):\n",
    "        \"\"\"Soft update model parameters.\n",
    "        θ_target = τ*θ_local + (1 - τ)*θ_target\n",
    "\n",
    "        Params\n",
    "        =======\n",
    "            local model (PyTorch model): weights will be copied from\n",
    "            target model (PyTorch model): weights will be copied to\n",
    "            tau (float): interpolation parameter\n",
    "\n",
    "        \"\"\"\n",
    "        for target_param, local_param in zip(target_model.parameters(),\n",
    "                                           local_model.parameters()):\n",
    "            target_param.data.copy_(tau*local_param.data + (1-tau)*target_param.data)\n",
    "            \n",
    "class ReplayBuffer:\n",
    "    \"\"\"Fixed -size buffe to store experience tuples.\"\"\"\n",
    "    \n",
    "    def __init__(self, action_size, buffer_size, batch_size, seed):\n",
    "        \"\"\"Initialize a ReplayBuffer object.\n",
    "        \n",
    "        Params\n",
    "        ======\n",
    "            action_size (int): dimension of each action\n",
    "            buffer_size (int): maximum size of buffer\n",
    "            batch_size (int): size of each training batch\n",
    "            seed (int): random seed\n",
    "        \"\"\"\n",
    "        \n",
    "        self.action_size = action_size\n",
    "        self.memory = deque(maxlen=buffer_size)\n",
    "        self.batch_size = batch_size\n",
    "        self.experiences = namedtuple(\"Experience\", field_names=[\"state\",\n",
    "                                                               \"action\",\n",
    "                                                               \"reward\",\n",
    "                                                               \"next_state\",\n",
    "                                                               \"done\"])\n",
    "        self.seed = random.seed(seed)\n",
    "        \n",
    "    def add(self,state, action, reward, next_state,done):\n",
    "        \"\"\"Add a new experience to memory.\"\"\"\n",
    "        e = self.experiences(state,action,reward,next_state,done)\n",
    "        self.memory.append(e)\n",
    "        \n",
    "    def sample(self):\n",
    "        \"\"\"Randomly sample a batch of experiences from memory\"\"\"\n",
    "        experiences = random.sample(self.memory,k=self.batch_size)\n",
    "        \n",
    "        states = torch.from_numpy(np.vstack([e.state for e in experiences if e is not None])).float().to(device)\n",
    "        actions = torch.from_numpy(np.vstack([e.action for e in experiences if e is not None])).long().to(device)\n",
    "        rewards = torch.from_numpy(np.vstack([e.reward for e in experiences if e is not None])).float().to(device)\n",
    "        next_states = torch.from_numpy(np.vstack([e.next_state for e in experiences if e is not None])).float().to(device)\n",
    "        dones = torch.from_numpy(np.vstack([e.done for e in experiences if e is not None]).astype(np.uint8)).float().to(device)\n",
    "        \n",
    "        return (states,actions,rewards,next_states,dones)\n",
    "    def __len__(self):\n",
    "        \"\"\"Return the current size of internal memory.\"\"\"\n",
    "        return len(self.memory)\n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Train the Agent with DQN\n",
    "\n",
    "Run the code below to train the agent from scratch."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "agent = Agent(state_size=8,action_size=4,seed=0)\n",
    "\n",
    "def dqn(n_episodes= 200, max_t = 1000, eps_start=1.0, eps_end = 0.01,\n",
    "       eps_decay=0.996):\n",
    "    \"\"\"Deep Q-Learning\n",
    "    \n",
    "    Params\n",
    "    ======\n",
    "        n_episodes (int): maximum number of training epsiodes\n",
    "        max_t (int): maximum number of timesteps per episode\n",
    "        eps_start (float): starting value of epsilon, for epsilon-greedy action selection\n",
    "        eps_end (float): minimum value of epsilon \n",
    "        eps_decay (float): mutiplicative factor (per episode) for decreasing epsilon\n",
    "        \n",
    "    \"\"\"\n",
    "    scores = [] # list containing score from each episode\n",
    "    scores_window = deque(maxlen=100) # last 100 scores\n",
    "    eps = eps_start\n",
    "    for i_episode in range(1, n_episodes+1):\n",
    "        state = env.reset()\n",
    "        score = 0\n",
    "        for t in range(max_t):\n",
    "            action = agent.act(state,eps)\n",
    "            next_state,reward,done,_ = env.step(action)\n",
    "            agent.step(state,action,reward,next_state,done)\n",
    "            ## above step decides whether we will train(learn) the network\n",
    "            ## actor (local_qnetwork) or we will fill the replay buffer\n",
    "            ## if len replay buffer is equal to the batch size then we will\n",
    "            ## train the network or otherwise we will add experience tuple in our \n",
    "            ## replay buffer.\n",
    "            state = next_state\n",
    "            score += reward\n",
    "            if done:\n",
    "                break\n",
    "            scores_window.append(score) ## save the most recent score\n",
    "            scores.append(score) ## sae the most recent score\n",
    "            eps = max(eps*eps_decay,eps_end)## decrease the epsilon\n",
    "            print('\\rEpisode {}\\tAverage Score {:.2f}'.format(i_episode,np.mean(scores_window)), end=\"\")\n",
    "            if i_episode %100==0:\n",
    "                print('\\rEpisode {}\\tAverage Score {:.2f}'.format(i_episode,np.mean(scores_window)))\n",
    "                \n",
    "            if np.mean(scores_window)>=200.0:\n",
    "                print('\\nEnvironment solve in {:d} epsiodes!\\tAverage score: {:.2f}'.format(i_episode-100,\n",
    "                                                                                           np.mean(scores_window)))\n",
    "                torch.save(agent.qnetwork_local.state_dict(),'checkpoint.pth')\n",
    "                break\n",
    "    return scores\n",
    "\n",
    "scores= dqn()\n",
    "\n",
    "#plot the scores\n",
    "fig = plt.figure()\n",
    "ax = fig.add_subplot(111)\n",
    "plt.plot(np.arange(len(scores)),scores)\n",
    "plt.ylabel('Score')\n",
    "plt.xlabel('Epsiode #')\n",
    "plt.show()\n",
    "                "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Watch a Smart Agent!\n",
    "In the next code cell, we will loda the trained weights from file to watch a smart agent!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#load the weights from file\n",
    "agent = Agent(state_size=8,action_size=4,seed=0)\n",
    "agent.qnetwork_local.load_state_dict(torch.load('checkpoint.pth'))\n",
    "\n",
    "for i in range(3):\n",
    "    state = env.reset()\n",
    "    img = plt.imshow(env.render(mode='rgb_array'))\n",
    "    for j in range(200):\n",
    "        action = agent.act(state)\n",
    "        img.set_data(env.render(mode='rbg_array'))\n",
    "        plt.axix('off')\n",
    "        display.display(plt.gcf())\n",
    "        display.clear_output(wait=True)\n",
    "        state,reward,done,_ = env.step(action)\n",
    "        if done:\n",
    "            break\n",
    "\n",
    "env.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Deep Q-Learning PipeLine"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. __Qnetwork__ -> Actor (Policy) model.\n",
    "    * Basically maps states and action space, its a neural network that works as Q-table, its input dimension is equal to dimensions of state space and out dimension is equal to action space dimensions.\n",
    "    * We basically keep two neural networks because while training our labels and predicted value are both function of neural network weights. To decouple the label from weights we keep two neural network.(__fixed q-targets__).\n",
    "2. __dqn_agent__ -> its a class with many methods and it helps the agent (dqn_agent) to **interact** and learn from the environment.\n",
    "3. __Replay Buffer__ ->Fixed size buffer to store experience tuples."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Different methods of dqn_agent\n",
    "* **\\_\\_init\\_\\_** method: We initialize the state_size,action and random seed.\n",
    "    * then we initialize two different q-network (qnetwork_local and qnetwork_target) One for mapping predictions and other for mapping targets.\n",
    "    * then we declare a optimizer and we only define this for parameters of qnetwork_local and later we will do softupdate and update the parameters for qnetwork_target using the parameters of qnetwork_local.\n",
    "    * then we initialize Replay buffer.\n",
    "    * then we initialize t_Step, which decides after how many steps our agent should learn from experiences.\n",
    "    \n",
    "* __Step__(self,state,action, reward, next_state, done)\n",
    "    * this method decides whether we will train(learn) the network actor (local_qnetwrok) and fill the replay buffer __or__ we will __only__ fill the replay buffer.\n",
    "    * We will only learn from the experiences if len of replay buffer is greater than batch_size __and__ t_Step is multiple of a number (of our choice , say after this many steps we want our agent to learn (for e.g 40 iterations).\n",
    "    \n",
    "* __learn__(self, experiences, gamma)\n",
    "    * this step is equivalent to the step in qlearning where we update the q_table(**state-action value**) for a state(S) after taking corresponding action(A) $Q[S,A] += \\alpha(R + \\gamma \\times(max_{a} Q[nextState]) - Q[S,A]) $ \n",
    "    * But here instead doing this step as our state space is continuous so we have non-linear function approximator for mapping the state, we do a back propagation on our neural network weights.\n",
    "    * And our __label__ is $max_a Q(Snext,A,w^-)*\\gamma + Reward$, where $Q(S,A,w^-)$ is the output from **qnetwork_target**.\n",
    "    * so the **dimension** of $Q(Snext,A,w^-)$ = \\[batch_size,dimension of actionSpace\\], that is how we have defined our **qnetwork**. but according to our formual target should be $max_a Q(S,A,w^-)*\\gamma + Reward$ so find $max_a Q(Snext,A,w^-)$, we do the following operation in __Pytorch__.\n",
    "    ```python \n",
    "    labels_next = self.qnetwork_target(next_State).detach().max(1)[0].unsqueeze(1)\n",
    "    ```\n",
    "    * After using the max along 1th dimension( among actions) our dimensions will be \\[batch_size\\] so to make it a dimension (batch_size,1) for Pytoch operations we have used unsqueeze(1) method.\n",
    "    * The states we get is of dimension (batch_size,state_dimension) one thing important to note here along batch_size we have different state at random order because of Replay Buffer (we have broken the **correlation of sequence order**)\n",
    "    * And this implementation $(1-dones)* labelsnext$ makes sure that there is no next state for **Terminating state**.\n",
    "    * After passing this state from `qnetwork_local` our output dimension will be (batch_size,actionSpace dimension) so in the this experience tuple which action our agent has taken we can choose that action by this command.\n",
    "    * `self.qnetwork_local(state).gather(1,actions)`\n",
    "    * so our output dimension will be (batch_size,1) -> predicted value.\n",
    "    * Now we can compute the loss and then we can use `backpropagation` to update our weights and hence is equivalent to updation **state action value**.(Q table)\n",
    "    * And then we do **softupdate** the update the **gradient** of **qnetwork_target**, remember we are only training one **sets weights** that is of **qnetwork_local**, so we need a way to update the weights of **qnetwork_target** and by updating those weights we are hoping that our target too improve after each steps as we are improving our predicted value, and the main idea we are using two network is because we want to decouple both target and predicted value from each other as both are the function weights, with fixed qtarget we are making it sure that are function different set of weights. So our network doesn't oscillates.\n",
    "    \n",
    "* __soft_update__(local_model,target_model, tau)\n",
    "    * One important thing to note is that when we were passing $NextState$ to the `qnetwork_taget` we were **not** calculating the **gradient** for each pass because we have wrapped with `with torch.no_grad()` and there is no need of calculating gradient.\n",
    "    * **tau** decides how much weightage will be given to the **qnetwork_local** and **qnetwork_target** weights.\n",
    "    ```python\n",
    "    for target_param,local_param in zip(target_model.parameters(),local_model.parameters()):\n",
    "        target_param.data.copy_(tau*local_param.data + (1.0-tau)*target_param.data)\n",
    "    ```\n",
    "    better than tensorflow :)\n",
    "\n",
    "* __act__(state,eps=0.)\n",
    "    * Returns the action for given state as per current policy.\n",
    "    * First we change our model in evaluation mode.\n",
    "    * then we change the state tensor from numpy to `torch.tensor` and the `.unsqueeze(1)` method is used to get a dimension along batch_size becuase in Pytorch you can only pass a input when it has a dimension which addresses the batch_size.\n",
    "    * And then we pass the state and get the crossponding action and note that we have use `qnetwork_local`.\n",
    "    * and we have a implementation of greedy action selection because we want to explore random action too. So that the agent gets more experience and `eps` hyperparameter controls this process.\n",
    "    * And as we know we decrease the `eps` gradually as our agent becomes smarter so we want to decrease the **exploration** and increase **exploitations**. Sounds fancy!  \n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Deep Q-Learning Improvements\n",
    "\n",
    "Several improvements to the original Deep-Q-Learning algorithm have been suggested\n",
    "- **Double DQN**\n",
    "    * Deep Q-Learning tends to overestimate action values. Double Q-Learning has been shown to work well in practice to help with this.\n",
    "- **Prioritized Experience Replay**\n",
    "     * Deep Q-learning samples experience transition *uniformly* from a replay memory.\n",
    "     * Prioritized experience replay is based on the idea that the agent can **learn** more effectively from some transition than others, and the more important transitions should be sampled with higher probability.\n",
    "- **Dueling DQN**\n",
    "    * Currently, in order to determine which states are (or are not ) valuable, we have to estimate the corresponding action values for *each action*. However, by replacing the traditional Deep Q-Network (DQN) architecture with a **dueling architecture**, we can asses the value of each state, without having to learn the effect of each action.\n",
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Double DQN\n",
    "* The basic idea here is while training the agent in early stages when agent is naive for target updation use, we use the action that maximizes the Q-value\\[next_state\\]. But in early in stage this is an noisy approximation so we tends to overestimate the Q-value.\n",
    "## Implementation\n",
    "* We select the best acton using one set of parameters $w$(qnetwork_local), but **evaluate** it with different set of parameters $w^-$(qnetwork_target).\n",
    "<br> $R + \\gamma q^{`}[S^{`},(argmax_a q^{`}(S^{`},a,w)),w^{`}]$\n",
    "* It's basically like having two separate function approximators that must agree on the best action.\n",
    "* If $w$ picks an action that is not the best according $w^-$, then Q-value returned is not that high.\n",
    "\n",
    "```python\n",
    "def learn(self, experiences, gamma):\n",
    "        \"\"\"Update value parameters using given batch of experience tuples.\n",
    "\n",
    "        Params\n",
    "        =======\n",
    "\n",
    "            experiences (Tuple[torch.Variable]): tuple of (s, a, r, s', done) tuples\n",
    "\n",
    "            gamma (float): discount factor\n",
    "        \"\"\"\n",
    "        states, actions, rewards, next_state, dones = experiences\n",
    "        ## TODO: compute and minimize the loss\n",
    "        criterion = torch.nn.MSELoss()\n",
    "        self.qnetwork_local.train()\n",
    "        self.qnetwork_target.eval()\n",
    "        #shape of output from the model (batch_size,action_dim) = (64,4)\n",
    "        predicted_targets = self.qnetwork_local(states).gather(1,actions)\n",
    "        \n",
    "        #################Updates for Double DQN learning###########################\n",
    "        self.qnetwork_local.eval()\n",
    "        with torch.no_grad():\n",
    "            actions_q_local = self.qnetwork_local(next_states).detach().max(1)[1].unsqueeze(1).long()\n",
    "            labels_next = self.qnetwork_target(next_states).gather(1,actions_q_local)\n",
    "        self.qnetwork_local.train()\n",
    "        ############################################################################\n",
    "\n",
    "        # .detach() ->  Returns a new Tensor, detached from the current graph.\n",
    "        labels = rewards + (gamma* labels_next*(1-dones))\n",
    "        \n",
    "        loss = criterion(predicted_targets,labels).to(device)\n",
    "        self.optimizer.zero_grad()\n",
    "        loss.backward()\n",
    "        self.optimizer.step()\n",
    "\n",
    "        # ------------------- update target network ------------------- #\n",
    "        self.soft_update(self.qnetwork_local,self.qnetwork_target,TAU)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tackling agent in unity environment "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from unityagent import UnityEnvironment\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "env = UnityEnvironment(file_name='./Banana.app')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Environment contains **brains** which are responsible for deciding the actions of their associated agents. Here we check for the first brain available, and set it as the default brain we will be controlling from Python."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#get the default brain\n",
    "brain_name = env.brain_name[0]\n",
    "brain = env.brains[brain_name]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#reset the environment \n",
    "env_info = env.reset(train_mode=True)[brain_name]\n",
    "\n",
    "# number of agents in the environment\n",
    "print('Number of agents:', len(env_info.agents))\n",
    "\n",
    "#number of actions\n",
    "action_size = brain.vector_action_space_size\n",
    "print(\"Number of actions:\", action_size)\n",
    "\n",
    "# examine the state space\n",
    "state = env_info.vector_observation[0]\n",
    "print('State look like:', state)\n",
    "state_size = len(state)\n",
    "print('State have length:', state_size)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Take a Random Actions in the Environment\n",
    "\n",
    "In the next code cell, we will learn how to use the Python API to control the agent and receive feedback from the environment.\n",
    "\n",
    "Once this cell is executed, we will watch the agent's performance, if it selects an action (uniformly) at random with each time step. A window should pop up that allows us to observe the agent, as it moves through environment.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "env_info = env.reset(train_mode=False)[brain_name] # reset the environment \n",
    "state = env_info.vector_observation[0]             # get the current state\n",
    "score = 0 \n",
    "while True:\n",
    "    action = np.random.randint(action_size)        # select an action\n",
    "    env_info= env.step(action)[brain_name]         # send the action to the environment\n",
    "    next_state = env_info.vector_observation[0]    # get the next state\n",
    "    reward = env.info.rewards[0]                   # get the reward\n",
    "    done = env_info.local_done[0]                  # see if the episode has finished\n",
    "    score += reward                                # update the score\n",
    "    state = next_state                             # roll over the state to next time step\n",
    "    if done :\n",
    "        break\n",
    "        "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}